Given k and two sets of ordering conditions, build a k x k matrix containing the integers 1..k exactly once so that both row and column conditions are satisfied. Return an empty matrix if impossible. Pattern focus: Kahn Topological Order. The row and column placements are both separate topological sorts.
k = matrix size and value range, rowConditions/colConditions = ordering constraints
a valid k x k matrix or an empty matrix
Example 1:
Input:
k = 3 rowConditions = [[1,2],[2,3]] colConditions = [[1,2],[2,3]]
Output:
[[1,0,0],[0,2,0],[0,0,3]]
Explanation:
The same order works for both rows and columns, so each number can be placed on the diagonal.
Example 2:
Input:
k = 3 rowConditions = [[1,2],[3,2]] colConditions = [[2,1],[3,2]]
Output:
[[0,0,1],[3,0,0],[0,2,0]]
Explanation:
This placement satisfies both row and column constraints.
Example 3:
Input:
k = 2 rowConditions = [[1,2]] colConditions = [[2,1]]
Output:
[]
Explanation:
The row and column constraints conflict, so no matrix exists.