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 != rightiThis 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time complexity: O(k!). Space complexity: O(k^2) due to matrix storage and recursive call stack.
| 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. |
Convert an Array Into a 2D Array With Conditions - Leetcode 2610 - Python • NeetCodeIO • 16,153 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