Solution: Build a Matrix with Conditions
Let’s solve the Build a Matrix with Conditions problem using the Topological Sort pattern.
We'll cover the following
Statement
You are given a positive integer
A 2D integer array
rowConditions
of size, where rowConditions[i] = [above[i], below[i]]
. This indicates thatabove[i]
must appear in a row abovebelow[i]
in the final matrix.A 2D integer array
colConditions
of size, where colConditions[i] = [left[i], right[i]]
. This indicates thatleft[i]
must appear in a column to the left ofright[i]
in the final matrix.
Both arrays contain integers ranging from
You need to construct a
For each pair
rowConditions[i]
, the integerabove[i]
must be located in a row strictly abovebelow[i]
.For each pair
colConditions[i]
, the integerleft[i]
must be positioned in a column strictly to the left ofright[i]
.
If it’s possible to create such a matrix, return any valid matrix. If it’s not possible, return an empty matrix.
Constraints:
rowConditions.length
,colConditions.length
rowConditions[i].length
colConditions[i].length
above[i]
,below[i]
,left[i]
,right[i]
above[i]
below[i]
left[i]
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:
We start by performing two separate topological sorts: one for the row conditions and one for the column conditions.
Each condition is represented as a directed edge in a graph where nodes are integers from
to , and an edge from to means that should come before . 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:
Unvisited nodes are marked as
. Nodes currently being visited (part of the current DFS path) are marked as
. Fully processed nodes are marked as
.
Once we have the topological orders for both the rows and columns, we use two dictionaries (
posRow
andposCol
) 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.For each integer from
to , if it appears in both the row and column orders, we place it in the corresponding position: matrix[posRow[num]][posCol[num]]
.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.