Build a Matrix With Conditions

The key idea

Rows and columns are two independent orderings. Build a directed graph for each set of conditions, topologically sort both; a number's row index is its position in the row order and its column index is its position in the column order. A cycle in either graph means no valid matrix.

Problem

You are given a positive integer k. You are also given:

- a 2D integer array rowConditions of size n where rowConditions[i] = [above_i, below_i], and
- a 2D integer array colConditions of size m where colConditions[i] = [left_i, right_i].

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:

- The number above_i should appear in a row that is strictly above the row that contains the number below_i for all i from 0 to n - 1.
- The number left_i should appear in a column that is strictly left of the column that contains the number right_i for all i from 0 to m - 1.

Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

Constraints

2 <= k <= 400
1 <= rowConditions.length, colConditions.length <= 10^4
rowConditions[i].length == colConditions[i].length == 2
1 <= above_i, below_i, left_i, right_i <= k
above_i != below_i
left_i != right_i

Examples

Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] Output: [[3,0,0],[0,0,1],[0,2,0]]

Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]] Output: []

Complexity

Time: O(k + R + C) Space: O(k + R + C)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →