Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given a positive integer k. You are also given:
rowConditions of size n where rowConditions[i] = [abovei, belowi], andcolConditions of size m where colConditions[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:
abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 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 != rightiProblem summary: You are given a positive integer k. You are also given: a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and a 2D integer array colConditions of size m where colConditions[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 abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1. The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1. Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Topological Sort
3 [[1,2],[3,2]] [[2,1],[3,2]]
3 [[1,2],[2,3],[3,1],[2,3]] [[2,1]]
course-schedule)course-schedule-ii)find-eventual-safe-states)loud-and-rich)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2392: Build a Matrix With Conditions
class Solution {
private int k;
public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
this.k = k;
List<Integer> row = f(rowConditions);
List<Integer> col = f(colConditions);
if (row == null || col == null) {
return new int[0][0];
}
int[][] ans = new int[k][k];
int[] m = new int[k + 1];
for (int i = 0; i < k; ++i) {
m[col.get(i)] = i;
}
for (int i = 0; i < k; ++i) {
ans[i][m[row.get(i)]] = row.get(i);
}
return ans;
}
private List<Integer> f(int[][] cond) {
List<Integer>[] g = new List[k + 1];
Arrays.setAll(g, key -> new ArrayList<>());
int[] indeg = new int[k + 1];
for (var e : cond) {
int a = e[0], b = e[1];
g[a].add(b);
++indeg[b];
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 1; i < indeg.length; ++i) {
if (indeg[i] == 0) {
q.offer(i);
}
}
List<Integer> res = new ArrayList<>();
while (!q.isEmpty()) {
for (int n = q.size(); n > 0; --n) {
int i = q.pollFirst();
res.add(i);
for (int j : g[i]) {
if (--indeg[j] == 0) {
q.offer(j);
}
}
}
}
return res.size() == k ? res : null;
}
}
// Accepted solution for LeetCode #2392: Build a Matrix With Conditions
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
}
# Accepted solution for LeetCode #2392: Build a Matrix With Conditions
class Solution:
def buildMatrix(
self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]
) -> List[List[int]]:
def f(cond):
g = defaultdict(list)
indeg = [0] * (k + 1)
for a, b in cond:
g[a].append(b)
indeg[b] += 1
q = deque([i for i, v in enumerate(indeg[1:], 1) if v == 0])
res = []
while q:
for _ in range(len(q)):
i = q.popleft()
res.append(i)
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
return None if len(res) != k else res
row = f(rowConditions)
col = f(colConditions)
if row is None or col is None:
return []
ans = [[0] * k for _ in range(k)]
m = [0] * (k + 1)
for i, v in enumerate(col):
m[v] = i
for i, v in enumerate(row):
ans[i][m[v]] = v
return ans
// Accepted solution for LeetCode #2392: Build a Matrix With Conditions
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2392: Build a Matrix With Conditions
// class Solution {
// private int k;
//
// public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
// this.k = k;
// List<Integer> row = f(rowConditions);
// List<Integer> col = f(colConditions);
// if (row == null || col == null) {
// return new int[0][0];
// }
// int[][] ans = new int[k][k];
// int[] m = new int[k + 1];
// for (int i = 0; i < k; ++i) {
// m[col.get(i)] = i;
// }
// for (int i = 0; i < k; ++i) {
// ans[i][m[row.get(i)]] = row.get(i);
// }
// return ans;
// }
//
// private List<Integer> f(int[][] cond) {
// List<Integer>[] g = new List[k + 1];
// Arrays.setAll(g, key -> new ArrayList<>());
// int[] indeg = new int[k + 1];
// for (var e : cond) {
// int a = e[0], b = e[1];
// g[a].add(b);
// ++indeg[b];
// }
// Deque<Integer> q = new ArrayDeque<>();
// for (int i = 1; i < indeg.length; ++i) {
// if (indeg[i] == 0) {
// q.offer(i);
// }
// }
// List<Integer> res = new ArrayList<>();
// while (!q.isEmpty()) {
// for (int n = q.size(); n > 0; --n) {
// int i = q.pollFirst();
// res.add(i);
// for (int j : g[i]) {
// if (--indeg[j] == 0) {
// q.offer(j);
// }
// }
// }
// }
// return res.size() == k ? res : null;
// }
// }
// Accepted solution for LeetCode #2392: Build a Matrix With Conditions
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;
}
Use this to step through a reusable interview workflow for this problem.
Repeatedly find a vertex with no incoming edges, remove it and its outgoing edges, and repeat. Finding the zero-in-degree vertex scans all V vertices, and we do this V times. Removing edges touches E edges total. Without an in-degree array, this gives O(V × E).
Build an adjacency list (O(V + E)), then either do Kahn's BFS (process each vertex once + each edge once) or DFS (visit each vertex once + each edge once). Both are O(V + E). Space includes the adjacency list (O(V + E)) plus the in-degree array or visited set (O(V)).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.