#2392
Build a Matrix With Conditions
specialist · 880 · lc hard +31 · verified · 79.3% accepted · 1,504 likes · top 90%
Description
You are given a positive integer k and two condition arrays:
- rowConditions of size n where rowConditions[i] = [abovei, belowi] requires that abovei appears in a row strictly above belowi.
- colConditions of size m where colConditions[i] = [lefti, righti] requires that lefti appears in a column strictly to the left of righti.
Build a k x k matrix containing integers 1 through k (each exactly once, with the rest filled with 0) that satisfies all row and column ordering conditions.
Return any such matrix. If no valid arrangement 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.
Code
1
2
3