Solution: Build a Matrix with Conditions

Statement

You are given a positive integer $k$ and two conditions:

• A 2D integer array row_conditions of size $n$, where row_conditions[i] = [above[i], below[i]]. This indicates that above[i] must appear in a row above below[i] in the final matrix.

• A 2D integer array col_conditions of size $m$, where col_conditions[i] = [left[i], right[i]]. This indicates that left[i] must appear in a column to the left of right[i] in the final matrix.

Both arrays contain integers ranging from $1$ to $k$.

You need to construct a $k \times k$ matrix that includes all the integers from $1$ to $k$ exactly once, with the remaining cells filled with zeros. The matrix must satisfy the following rules:

• For each pair row_conditions[i], the integer above[i] must be located in a row strictly above below[i].

• For each pair col_conditions[i], the integer left[i] must be positioned in a column strictly to the left of right[i].

If it’s possible to create such a matrix, return any valid matrix. If it’s not possible, return an empty matrix.

Constraints:

• $2 \leq k \leq 400$

• $1 \leq$ row_conditions.length, col_conditions.length $\leq 10^4$

• row_conditions[i].length $=$ col_conditions[i].length $= 2$

• $1 \leq$ above[i], below[i], left[i], right[i] $\leq k$

• above[i] $\neq$ below[i]

• left[i] $\neq$ right[i]

Solution

The essence of this solution lies in treating the row and column conditions as directed graphs, where the nodes represent values and the edges represent the constraints (above–below and left–right). By performing two topological sorts on these graphs, the solution aims to find valid orders for placing values in the matrix.

The topological sorts help detect cycles, ensuring that the constraints are logically consistent and achievable. Once valid orders are determined, the solution maps each value to its corresponding row and column position and places it in the matrix. If a cycle is detected in either sort, it indicates conflicting constraints, making it impossible to create a valid matrix, and thus an empty matrix is returned.

Here’s the detailed algorithm that we’ll use to solve the given problem:

1. We start by performing two separate topological sorts: one for the row conditions and one for the column conditions.

2. Each condition is represented as a directed edge in a graph where nodes are integers from $1$ to $k$, and an edge from $x$ to $y$ means that $x$ should come before $y$.

3. A depth-first search (DFS) is conducted for each node to find a valid topological ordering. During DFS, we ensure that there are no cycles in the precedence constraints by tracking the visitation state of nodes:

   1. Unvisited nodes are marked as $0$.

   2. Nodes currently being visited (part of the current DFS path) are marked as$1$.

   3. Fully processed nodes are marked as $2$.

4. Once we have the topological orders for both the rows and columns, we use two dictionaries (pos_row and pos_col) to map each number to its respective position in the matrix. These dictionaries allow for constant time access when determining the placement of each integer.

5. For each integer from $1$ to $k$, if it appears in both the row and column orders, we place it in the corresponding position: matrix[pos_row[num]][pos_col[num]].

6. If either of the topological sorts fails (returns an empty result due to cycles), the function immediately returns an empty matrix. Otherwise, the matrix is returned with the integers correctly placed according to the precedence constraints.

Now, let’s look at the following illustration to get a better understanding of the solution: