Build a Matrix With Conditions solution and explanation
Google
9 more videos on this problem
Build a Matrix With Conditions - Leetcode 2392 - PythonNeetCodeIO · 25:12 · 12K views
Build a Matrix With Conditions | BFS | DFS | Detailed Explanation | Leetcode 2392 | codestorywithMIKcodestorywithMIK · 40:50 · 10K views
2392. Build a Matrix With Conditions | Topological Sort | Graph | Easy & Clean CodeAryan Mittal · 16:46 · 6K views
Leetcode 2392. Build A Matrix With Conditions | Weekly Contest 308.Code with Alisha · 27:46 · 3K views
2392. Build a Matrix With Conditions (Leetcode Hard)Programming Live with Larry · 18:14 · 748 views
Build a Matrix With Conditions || 2392 || Leetcode Contest Hard|| CPP || Most Intuitive Solution 🤩🤩Coding Techniques with Komal | Newton School · 28:21 · 498 views
Daily Leetcode #1573: Jul 21, 2024 - 2392. Build a Matrix With ConditionsProgramming Live with Larry · 12:16 · 412 views
Build a Matrix With Conditions (LeetCode 2392) (Hard) (Graph) (Kahn's Algorithm) (Topological Sort)CodeWithARB · 44:39 · 248 views
Leetcode 2392: Build a Matrix With ConditionsAlgorithms Casts · 23:25 · 239 views
LeetCode 2392 - Build a Matrix With Conditions - JavaAlpha-Code · 16:31 · 193 views
The problem
You are given a positive integer k. You are also given:
- a 2D integer array
rowConditionsof sizenwhererowConditions[i] = [abovei, belowi], and - a 2D integer array
colConditionsof sizemwherecolConditions[i] = [lefti, righti].
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
aboveishould appear in a row that is strictly above the row at which the numberbelowiappears for allifrom0ton - 1. - The number
leftishould appear in a column that is strictly left of the column at which the numberrightiappears for allifrom0tom - 1.
Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.
Example 1:
Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] Output: [[3,0,0],[0,0,1],[0,2,0]] Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions. The row conditions are the following: - Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix. - Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix. The column conditions are the following: - Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix. - Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix. Note that there may be multiple correct answers.
Example 2:
Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]] Output: [] Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied. No matrix can satisfy all the conditions, so we return the empty matrix.
Constraints:
2 <= k <= 4001 <= rowConditions.length, colConditions.length <= 104rowConditions[i].length == colConditions[i].length == 21 <= abovei, belowi, lefti, righti <= kabovei != belowilefti != righti
Approach overview
Problem Overview: You must place numbers from 1..k in a k x k matrix. Some constraints require one number to appear above another (row conditions) or to the left of another (column conditions). The challenge is arranging each number exactly once so both sets of ordering constraints are satisfied.
Approach 1: Graph Representation and Topological Sort (O(k + R + C) time, O(k + R + C) space)
Model both constraint lists as directed graphs. One graph represents row precedence (a must appear above b), and another represents column precedence (a must appear left of b). Run a topological sort on each graph to compute a valid ordering of numbers for rows and columns. If either graph contains a cycle, no valid matrix exists.
After obtaining the two topological orders, map each number to its row index and column index. Create an empty k x k matrix and place number x at position (rowIndex[x], colIndex[x]). This works because the row ordering guarantees vertical constraints while the column ordering guarantees horizontal constraints. The algorithm processes each node and edge once, giving linear complexity relative to the number of constraints.
This approach relies heavily on graph modeling and topological sort. The matrix construction step is straightforward once both orderings are known.
Approach 2: Backtracking with Constraint Propagation (Exponential time, O(k^2) space)
Another way is to treat the matrix as a constraint satisfaction problem. Try placing numbers into cells while verifying that partial placements do not violate row or column precedence rules. When placing a value, propagate constraints by checking if the required relative positions are still possible. If a conflict appears, backtrack and try a different placement.
This method explores permutations of placements and prunes invalid states early using constraint checks. While workable for very small k, the search space grows rapidly and quickly becomes impractical. It mainly helps build intuition about how ordering constraints restrict placements in a matrix.
Recommended for interviews: The graph + topological sort approach is the expected solution. It converts ordering constraints into two independent DAG problems and solves them in linear time. Showing the brute-force backtracking idea demonstrates understanding of constraint satisfaction, but the optimal solution proves you recognize when a dependency problem should be solved with DAG ordering.
Approach 1: Graph Representation and Topological Sort
This approach involves representing row and column conditions as directed graphs. You perform a topological sort on these graphs to determine valid row and column positions for each number from 1 to k. If cycle detection reveals any contradictions, it indicates that it's impossible to build the matrix.
# Python code omitted for brevity// Java code omitted for brevity// C++ code omitted for brevity// JavaScript code omitted for brevity/* C code omitted for brevity */// C# code omitted for brevityIn Python, we utilize dictionaries to handle graph representation and perform topological sorting, checking for cycles using indegrees.
Time complexity: O(k + n + m). Space complexity: O(k + n + m).
Approach 2: Default Approach
function buildMatrix(k: number, rowConditions: number[][], colConditions: number[][]): number[][] {
function f(cond) {
const g = Array.from({ length: k + 1 }, () => []);
const indeg = new Array(k + 1).fill(0);
for (const [a, b] of cond) {
g[a].push(b);
++indeg[b];
}
const q = [];
for (let i = 1; i < indeg.length; ++i) {
if (indeg[i] == 0) {
q.push(i);
}
}
const res = [];
while (q.length) {
for (let n = q.length; n; --n) {
const i = q.shift();
res.push(i);
for (const j of g[i]) {
if (--indeg[j] == 0) {
q.push(j);
}
}
}
}
return res.length == k ? res : [];
}
const row = f(rowConditions);
const col = f(colConditions);
if (!row.length || !col.length) return [];
const ans = Array.from({ length: k }, () => new Array(k).fill(0));
const m = new Array(k + 1).fill(0);
for (let i = 0; i < k; ++i) {
m[col[i]] = i;
}
for (let i = 0; i < k; ++i) {
ans[i][m[row[i]]] = row[i];
}
return ans;
}func buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {
f := func(cond [][]int) []int {
g := make([][]int, k+1)
indeg := make([]int, k+1)
for _, e := range cond {
a, b := e[0], e[1]
g[a] = append(g[a], b)
indeg[b]++
}
q := []int{}
for i, v := range indeg[1:] {
if v == 0 {
q = append(q, i+1)
}
}
res := []int{}
for len(q) > 0 {
for n := len(q); n > 0; n-- {
i := q[0]
q = q[1:]
res = append(res, i)
for _, j := range g[i] {
indeg[j]--
if indeg[j] == 0 {
q = append(q, j)
}
}
}
}
if len(res) == k {
return res
}
return []int{}
}
row := f(rowConditions)
col := f(colConditions)
if len(row) == 0 || len(col) == 0 {
return [][]int{}
}
m := make([]int, k+1)
for i, v := range col {
m[v] = i
}
ans := make([][]int, k)
for i := range ans {
ans[i] = make([]int, k)
}
for i, v := range row {
ans[i][m[v]] = v
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Graph Representation and Topological Sort | Time complexity: O(k + n + m). Space complexity: O(k + n + m). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Representation + Topological Sort | O(k + R + C) | O(k + R + C) | General and optimal solution when ordering constraints form DAG relationships |
| Backtracking with Constraint Propagation | Exponential | O(k^2) | Useful for conceptual understanding or very small k where brute-force search is feasible |
Frequently asked questions
Is Build a Matrix With Conditions easy or hard?
The problem is labeled Hard because it requires recognizing that two independent topological sorts can determine matrix coordinates. Candidates must correctly detect cycles, maintain ordering constraints, and combine the results into a valid matrix layout.
Build a Matrix With Conditions Python/Java solution
Most implementations build adjacency lists for row and column constraints, compute topological order using BFS (Kahn's algorithm), and then construct the matrix using index mappings. The same logic works in Python, Java, C++, C#, or JavaScript with minor syntax differences.
How to solve Build a Matrix With Conditions in O(n)?
Treat row and column constraints as two separate DAG ordering problems. Run topological sort on the row graph and the column graph to produce two valid sequences of numbers. Map each value to its row and column index and place it directly in a k×k matrix. Since each edge and node is processed once, the algorithm runs in linear time relative to the number of constraints.
What is the best approach for Build a Matrix With Conditions?
The optimal approach models row and column constraints as two directed graphs and performs topological sort on each. The row ordering determines vertical positions and the column ordering determines horizontal positions. If either graph contains a cycle, the constraints are impossible. This solution runs in O(k + R + C) time where R and C are the number of row and column conditions.
Is Build a Matrix With Conditions asked at Google/Amazon/Meta?
Problems involving topological ordering of constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often involve scheduling tasks, resolving dependencies, or validating precedence rules in graphs.
What data structure is used in Build a Matrix With Conditions?
The core data structures are adjacency lists for representing directed graphs and a queue for Kahn's topological sort algorithm. Additional arrays store in-degrees and map each value to its computed row and column index before filling the matrix.
What is the time complexity of Build a Matrix With Conditions?
Using the graph and topological sort approach, the complexity is O(k + R + C). Each node from 1..k is processed once and every constraint edge is visited during BFS or DFS topological sorting. Building the final matrix takes O(k^2) initialization but only O(k) placements.