Watch 10 video solutions for Build a Matrix With Conditions, a hard level problem involving Array, Graph, Topological Sort. This walkthrough by NeetCodeIO has 11,995 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a positive integer k. You are also given:
rowConditions of size n where rowConditions[i] = [abovei, belowi], andcolConditions of size m where colConditions[i] = [lefti, righti].The two arrays contain integers from 1 to k.
You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0.
The matrix should also satisfy the following conditions:
abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.
Example 1:
Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] Output: [[3,0,0],[0,0,1],[0,2,0]] Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions. The row conditions are the following: - Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix. - Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix. The column conditions are the following: - Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix. - Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix. Note that there may be multiple correct answers.
Example 2:
Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]] Output: [] Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied. No matrix can satisfy all the conditions, so we return the empty matrix.
Constraints:
2 <= k <= 4001 <= rowConditions.length, colConditions.length <= 104rowConditions[i].length == colConditions[i].length == 21 <= abovei, belowi, lefti, righti <= kabovei != belowilefti != rightiProblem Overview: You must place numbers from 1..k in a k x k matrix. Some constraints require one number to appear above another (row conditions) or to the left of another (column conditions). The challenge is arranging each number exactly once so both sets of ordering constraints are satisfied.
Approach 1: Graph Representation and Topological Sort (O(k + R + C) time, O(k + R + C) space)
Model both constraint lists as directed graphs. One graph represents row precedence (a must appear above b), and another represents column precedence (a must appear left of b). Run a topological sort on each graph to compute a valid ordering of numbers for rows and columns. If either graph contains a cycle, no valid matrix exists.
After obtaining the two topological orders, map each number to its row index and column index. Create an empty k x k matrix and place number x at position (rowIndex[x], colIndex[x]). This works because the row ordering guarantees vertical constraints while the column ordering guarantees horizontal constraints. The algorithm processes each node and edge once, giving linear complexity relative to the number of constraints.
This approach relies heavily on graph modeling and topological sort. The matrix construction step is straightforward once both orderings are known.
Approach 2: Backtracking with Constraint Propagation (Exponential time, O(k^2) space)
Another way is to treat the matrix as a constraint satisfaction problem. Try placing numbers into cells while verifying that partial placements do not violate row or column precedence rules. When placing a value, propagate constraints by checking if the required relative positions are still possible. If a conflict appears, backtrack and try a different placement.
This method explores permutations of placements and prunes invalid states early using constraint checks. While workable for very small k, the search space grows rapidly and quickly becomes impractical. It mainly helps build intuition about how ordering constraints restrict placements in a matrix.
Recommended for interviews: The graph + topological sort approach is the expected solution. It converts ordering constraints into two independent DAG problems and solves them in linear time. Showing the brute-force backtracking idea demonstrates understanding of constraint satisfaction, but the optimal solution proves you recognize when a dependency problem should be solved with DAG ordering.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Representation + Topological Sort | O(k + R + C) | O(k + R + C) | General and optimal solution when ordering constraints form DAG relationships |
| Backtracking with Constraint Propagation | Exponential | O(k^2) | Useful for conceptual understanding or very small k where brute-force search is feasible |