Solution: Build a Matrix with Conditions

Let’s solve the Build a Matrix with Conditions problem using the Topological Sort pattern.

Statement

You are given a positive integer kk and two conditions:

  • A 2D integer array rowConditions of size nn, where rowConditions[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 colConditions of size mm, where colConditions[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 11 to kk.

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

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

  • For each pair colConditions[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:

  • 2k4002 \leq k \leq 400

  • 11 \leq rowConditions.length, colConditions.length 104\leq 10^4

  • rowConditions[i].length == colConditions[i].length =2= 2

  • 11 \leq above[i], below[i], left[i], right[i] k\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 11 to kk, and an edge from xx to yy means that xx should come before yy.

  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 00.

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

    3. Fully processed nodes are marked as 22.

  4. Once we have the topological orders for both the rows and columns, we use two dictionaries (posRow and posCol) 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 11 to kk, if it appears in both the row and column orders, we place it in the corresponding position: matrix[posRow[num]][posCol[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:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.