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.
This approach involves representing row and column conditions as directed graphs. You perform a topological sort on these graphs to determine valid row and column positions for each number from 1 to k. If cycle detection reveals any contradictions, it indicates that it's impossible to build the matrix.
This code uses an adjacency list to represent dependencies between numbers. The algorithm then performs topological sorting using a queue and processes elements based on their dependencies.
The algorithm has a time complexity of O(k + n + m), where k is the size of the matrix, n is the number of row conditions, and m is the number of column conditions. The space complexity is O(k + n + m) for storing the conditions and dependencies.
This approach considers using backtracking to build the matrix. For each valid permutation of numbers, it ensures constraints are satisfied and adjusts dynamically by propagating constraints to subsequent steps.
The code uses recursion combined with backtracking to explore all permutations and uses constraint-checking to prune invalid paths efficiently.
Time complexity: O(k!). Space complexity: O(k^2) due to matrix storage and recursive call stack.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Graph Representation and Topological Sort | The algorithm has a time complexity of O(k + n + m), where k is the size of the matrix, n is the number of row conditions, and m is the number of column conditions. The space complexity is O(k + n + m) for storing the conditions and dependencies. |
| Backtracking with Constraints Propagation | Time complexity: O(k!). Space complexity: O(k^2) due to matrix storage and recursive call stack. |
| Default Approach | — |
| 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 |
Build a Matrix With Conditions - Leetcode 2392 - Python • NeetCodeIO • 11,995 views views
Watch 9 more video solutions →Practice Build a Matrix With Conditions with our built-in code editor and test cases.
Practice on FleetCode