Build a Matrix With Conditions

Build a Matrix With Conditions

What is this problem about?

You are given an integer $k$ and two sets of conditions: rowConditions and colConditions. Each condition is a pair [u, v] meaning $u$ must appear in a row (or column) above (or to the left of) $v$. You need to build a $k imes k$ matrix containing the numbers 1 to $k$ that satisfies all conditions. If no such matrix exists, return an empty array.

Why is this asked in interviews?

This "Hard" problem is used by Google and Meta to test your knowledge of Graph theory and your ability to decouple multi-dimensional constraints. It requires you to realize that the row positions and column positions can be determined completely independently of each other using the same algorithm.

Algorithmic pattern used

The core pattern is Topological Sort. You treat the row conditions as a directed graph where an edge u -> v means $u$ comes before $v$. You perform a topological sort to find a valid linear ordering of the numbers 1 to $k$ for the rows. You do the same for the column conditions. If either graph has a cycle (meaning topological sort is impossible), then no valid matrix exists. Finally, you use the resulting orderings to place each number i at coordinates (row_index[i], col_index[i]).

Example explanation

$k = 3$, rowConditions = [[1, 2]], colConditions = [[2, 1]]

1. Row order: 1 must be above 2. A valid order: [3, 1, 2]. (3 can go anywhere).
2. Col order: 2 must be left of 1. A valid order: [3, 2, 1].
3. Mapping:
   • 1: row index 1, col index 2. Position: (1, 2).
   • 2: row index 2, col index 1. Position: (2, 1).
   • 3: row index 0, col index 0. Position: (0, 0).

Common mistakes candidates make

A common error is trying to solve the row and column constraints simultaneously, which is much more difficult. Another is failing to detect cycles in the graph, which should lead to an empty result. Using Kahn's algorithm or DFS for topological sort is fine, but you must ensure you handle all $k$ numbers, even those not mentioned in the conditions.

Interview preparation tip

Master Topological Sort. It's the standard tool for any problem involving "precedence" or "orderings." Also, remember that in 2D grid problems, you can often solve the X and Y dimensions independently if the constraints don't link them together.