Build a Matrix with Conditions

Build a Matrix with Conditions hard

Description

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 × 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 at which the number below_i appears for all i from 0 to n - 1.
The number left_i should appear in a column that is strictly left of the column at which the number right_i appears for all i from 0 to m - 1.

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

Examples

> Case 1:
    k = 3
    rowConditions = [[1, 2], [3, 2]]
    colConditions = [[2, 1], [3, 2]]
    Output: [[3, 0, 0], [0, 0, 1], [0, 2, 0]]
    Explanation:
        Row order: 1 above 2, 3 above 2. So 1 and 3 are in higher rows than 2.
        Col order: 2 is in a column left of 1; 3 is in a column left of 2.
        One valid arrangement: number 3 at (0, 0); number 1 at (1, 2); number 2 at (2, 1).

Constraints

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

State design

Two independent topological sorts:

Row order: topo-sort the row constraints. Output → which row each number goes to.
Column order: topo-sort the column constraints. Output → which column each number goes to.

Each topo sort gives a list order[] where order[i] is the number at position i. Invert it to get pos[number] = i. Then place each number at (rowPos[number], colPos[number]).

If either topo sort detects a cycle, return the empty matrix.

Code

The decomposition insight: rows and columns are independent — row constraints only constrain row positions, column constraints only constrain column positions. So we can topo-sort each independently. The 2D placement is then just looking up (rowPos[x], colPos[x]) per number.

If either ordering fails (cycle), the whole problem fails.

Analysis

Time: O(k + n + m) where n = row conditions, m = col conditions. Plus O(k²) for filling the matrix.
Space: O(k² + n + m).

Same skin

Course Schedule II — single topo sort, output the order.
Alien Dictionary — extract constraints from a list, then topo sort.
Sort Items by Groups Respecting Dependencies — two-level topo sort (groups + items within groups).
Sequence Reconstruction — single topo sort with uniqueness check.

This is one of the cleanest “compose multiple topo sorts” problems on LeetCode. Once you see that rows and columns are independent, the algorithm follows naturally — and the rest is just bookkeeping.

Longest Increasing Path in a Matrix Loud and Rich