Editorial
Core insight
Build a Matrix With Conditions · Graph Traversal Patterns (DFS & BFS)
Core Insight for Build a Matrix With Conditions
The critical insight for LeetCode 2392 is independence. The constraints affecting row placement are entirely independent of the constraints affecting column placement.
- Decomposition: We can solve for the row indices of numbers completely ignoring their column positions, and vice versa.
- Graph Representation:
rowConditionscan be viewed as a directed graph where an edge means must appear in a row index strictly smaller than .colConditionsforms a second, separate directed graph where means must appear in a column index strictly smaller than .
- Topological Sort: A topological sort of the "row graph" gives us a valid sequence of numbers from top to bottom. If the sort returns
[3, 1, 2], it means number 3 goes in row 0, number 1 in row 1, and number 2 in row 2. We apply the same logic to the "column graph". - Cycle Detection: If either graph contains a cycle (e.g., 1 is above 2, 2 is above 3, and 3 is above 1), a topological sort is impossible, and no valid matrix exists.
Visual Description: Imagine the numbers to as nodes in a graph. For the row conditions, draw a directed arrow from the "above" number to the "below" number. Kahn's algorithm visualizes this by identifying nodes with no incoming arrows (in-degree 0)—these are the candidates for the topmost available row. Once a number is placed, we remove it and its outgoing arrows, potentially freeing up new numbers to be placed in the next row. This process repeats layer by layer.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 2392: Build a Matrix With Conditions Solution & Explanation
Problem Overview
TL;DR: The optimal solution treats row and column constraints as two independent Topological Sort problems, determining the specific row and column index for each number separately before combining them into the final matrix.
In the LeetCode 2392 problem, "Build a Matrix With Conditions," you are tasked with constructing a matrix containing numbers from to . You are given two sets of constraints: rowConditions, which dictate the relative vertical order of numbers, and colConditions, which dictate the relative horizontal order. If number must be above , needs a smaller row index than . Similarly, if must be left of , needs a smaller column index.
This is a popular interview question because it tests the ability to decompose a complex 2D problem into two simpler 1D graph problems.
Brute Force Approach for Build a Matrix With Conditions
A naive approach attempts to place numbers through into the matrix grid by trying every possible permutation of placements until one satisfies all conditions. Alternatively, one might try to generate all permutations of the numbers for the rows and all permutations for the columns.
Pseudo-code for Naive Backtracking:
function solve(index, matrix):
if index > k:
if checkAllConditions(matrix): return matrix
return null
for r from 0 to k-1:
for c from 0 to k-1:
if matrix[r][c] is empty:
matrix[r][c] = index
result = solve(index + 1, matrix)
if result is valid: return result
matrix[r][c] = empty // backtrack
return nullTime Complexity: The complexity is roughly or depending on the specific permutation strategy. With , is astronomically large (far exceeding the number of atoms in the universe).
Why it fails: The constraints allow for up to 400. Any exponential or factorial solution will immediately result in a Time Limit Exceeded (TLE). We need a polynomial time solution, specifically one close to linear relative to the number of constraints.
Algorithm Strategy: Graph BFS - Topological Sort (Kahn's Algorithm)
We will implement Kahn's Algorithm twice: once for rows and once for columns.
- Graph Construction: For the given conditions (row or col), build an adjacency list and an
in_degreearray. Thein_degreearray tracks how many prerequisites each number has. - Queue Initialization: Push all numbers with an
in_degreeof 0 into a queue. These numbers have no dependencies and can be placed first. - Process Queue (BFS):
- Pop a number
ufrom the queue and add it to the result list. - Iterate through all neighbors
vofu(where ). - Decrement the
in_degreeofv. - If
v'sin_degreebecomes 0, pushvinto the queue.
- Pop a number
- Validation: If the size of the result list is less than , a cycle exists. Return an empty matrix immediately.
- Matrix Assembly:
- Map each number to its index in the row topological sort (its row coordinate).
- Map each number to its index in the column topological sort (its column coordinate).
- Initialize a matrix with zeros.
- Place each number at its calculated
(row, col)coordinate.
Execution Flow
Let's trace the logic with , rowConditions=[[1,2], [3,2]], colConditions=[[2,1], [3,2]].
-
Solve Row Constraints:
- Edges: , .
- In-degrees: .
- Queue initially: (order in queue doesn't matter for validity).
- Pop 1: Add to
rowOrder. Decrement 2's degree (now 1). - Pop 3: Add to
rowOrder. Decrement 2's degree (now 0). Push 2. - Pop 2: Add to
rowOrder. rowOrder: (Indices: 1 is at row 0, 3 at row 1, 2 at row 2).
-
Solve Column Constraints:
- Edges: , .
- In-degrees: .
- Queue initially: .
- Pop 3: Add to
colOrder. Decrement 2's degree (now 0). Push 2. - Pop 2: Add to
colOrder. Decrement 1's degree (now 0). Push 1. - Pop 1: Add to
colOrder. colOrder: (Indices: 3 is at col 0, 2 at col 1, 1 at col 2).
-
Construct Matrix:
- Number 1: Row index 0 (from
rowOrder), Col index 2 (fromcolOrder). - Number 2: Row index 2, Col index 1.
- Number 3: Row index 1, Col index 0.
- Result:
0 0 1 3 0 0 0 2 0
(Note: This output differs slightly from the example explanation because topological sort order for independent nodes is not unique, but both are valid).
- Number 1: Row index 0 (from
Proof of Correctness
The algorithm relies on the property of Topological Sort. A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge , comes before in the ordering.
By using the index in the topological sort as the matrix coordinate:
- If
rowConditionsspecify above , the graph has edge . The sort places before . Thus,rowIndex[u] < rowIndex[v]. The condition is satisfied. - The same logic applies to
colConditions. - Since we use Kahn's algorithm, we naturally detect cycles (if the result length ). If a cycle exists, no linear ordering satisfies the conditions, so we correctly return empty.
Pattern Reuse Notes
The Graph BFS - Topological Sort pattern is essential for solving dependency resolution problems.
- LeetCode 207: Course Schedule: Determines if a valid schedule exists (cycle detection).
- LeetCode 210: Course Schedule II: Returns the specific order of courses (exactly like the row/col ordering here).
- LeetCode 269: Alien Dictionary: Constructs an order of characters based on word precedence rules.
- LeetCode 310: Minimum Height Trees: Uses a similar "peeling onion" strategy (removing leaf nodes) akin to processing 0 in-degree nodes.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 2392
1#include <vector>
2#include <queue>
3#include <unordered_map>
4
5using namespace std;
6
7class Solution {
8public:
9 // Helper function to perform Kahn's Algorithm (Topological Sort)
10 vector<int> topologicalSort(int k, vector<vector<int>>& conditions) {
11 vector<vector<int>> adj(k + 1);
12 vector<int> inDegree(k + 1, 0);
13
14 // Build Graph
15 for (const auto& cond : conditions) {
16 int u = cond[0];
17 int v = cond[1];
18 adj[u].push_back(v);
19 inDegree[v]++;
20 }
21
22 // Initialize Queue with nodes having 0 in-degree
23 queue<int> q;
24 for (int i = 1; i <= k; i++) {
25 if (inDegree[i] == 0) {
26 q.push(i);
27 }
28 }
29
30 vector<int> order;
31 while (!q.empty()) {
32 int u = q.front();
33 q.pop();
34 order.push_back(u);
35
36 for (int v : adj[u]) {
37 inDegree[v]--;
38 if (inDegree[v] == 0) {
39 q.push(v);
40 }
41 }
42 }
43
44 // If we didn't visit all k nodes, there's a cycle
45 if (order.size() != k) return {};
46 return order;
47 }
48
49 vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
50 vector<int> rowOrder = topologicalSort(k, rowConditions);
51 vector<int> colOrder = topologicalSort(k, colConditions);
52
53 // If either sort failed due to a cycle
54 if (rowOrder.empty() || colOrder.empty()) return {};
55
56 // Map value -> index
57 vector<int> rowIndex(k + 1), colIndex(k + 1);
58 for (int i = 0; i < k; i++) {
59 rowIndex[rowOrder[i]] = i;
60 colIndex[colOrder[i]] = i;
61 }
62
63 // Build result matrix
64 vector<vector<int>> matrix(k, vector<int>(k, 0));
65 for (int i = 1; i <= k; i++) {
66 matrix[rowIndex[i]][colIndex[i]] = i;
67 }
68
69 return matrix;
70 }
71};Java Solution for LeetCode 2392
1import java.util.*;
2
3class Solution {
4 // Helper function for Kahn's Algorithm
5 private List<Integer> topologicalSort(int k, int[][] conditions) {
6 List<List<Integer>> adj = new ArrayList<>();
7 for (int i = 0; i <= k; i++) {
8 adj.add(new ArrayList<>());
9 }
10 int[] inDegree = new int[k + 1];
11
12 for (int[] cond : conditions) {
13 int u = cond[0];
14 int v = cond[1];
15 adj.get(u).add(v);
16 inDegree[v]++;
17 }
18
19 Queue<Integer> q = new LinkedList<>();
20 for (int i = 1; i <= k; i++) {
21 if (inDegree[i] == 0) {
22 q.add(i);
23 }
24 }
25
26 List<Integer> order = new ArrayList<>();
27 while (!q.isEmpty()) {
28 int u = q.poll();
29 order.add(u);
30
31 for (int v : adj.get(u)) {
32 inDegree[v]--;
33 if (inDegree[v] == 0) {
34 q.add(v);
35 }
36 }
37 }
38
39 if (order.size() != k) return new ArrayList<>();
40 return order;
41 }
42
43 public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
44 List<Integer> rowOrder = topologicalSort(k, rowConditions);
45 List<Integer> colOrder = topologicalSort(k, colConditions);
46
47 if (rowOrder.isEmpty() || colOrder.isEmpty()) {
48 return new int[0][0];
49 }
50
51 // Map value to its determined index
52 int[] rowIndex = new int[k + 1];
53 int[] colIndex = new int[k + 1];
54
55 for (int i = 0; i < k; i++) {
56 rowIndex[rowOrder.get(i)] = i;
57 colIndex[colOrder.get(i)] = i;
58 }
59
60 int[][] matrix = new int[k][k];
61 for (int i = 1; i <= k; i++) {
62 matrix[rowIndex[i]][colIndex[i]] = i;
63 }
64
65 return matrix;
66 }
67}Python Solution for LeetCode 2392
1from collections import deque, defaultdict
2
3class Solution:
4 def buildMatrix(self, k: int, rowConditions: list[list[int]], colConditions: list[list[int]]) -> list[list[int]]:
5
6 def topological_sort(conditions):
7 adj = defaultdict(list)
8 in_degree = {i: 0 for i in range(1, k + 1)}
9
10 for u, v in conditions:
11 adj[u].append(v)
12 in_degree[v] += 1
13
14 queue = deque([node for node in in_degree if in_degree[node] == 0])
15 order = []
16
17 while queue:
18 u = queue.popleft()
19 order.append(u)
20
21 for v in adj[u]:
22 in_degree[v] -= 1
23 if in_degree[v] == 0:
24 queue.append(v)
25
26 # Check for cycle
27 if len(order) != k:
28 return []
29 return order
30
31 row_order = topological_sort(rowConditions)
32 col_order = topological_sort(colConditions)
33
34 if not row_order or not col_order:
35 return []
36
37 # Map values to their indices
38 row_pos = {val: i for i, val in enumerate(row_order)}
39 col_pos = {val: i for i, val in enumerate(col_order)}
40
41 matrix = [[0] * k for _ in range(k)]
42
43 for num in range(1, k + 1):
44 r, c = row_pos[num], col_pos[num]
45 matrix[r][c] = num
46
47 return matrix