Build a Matrix With Conditions
Problem
You are given a positive integer k and two lists of pairs. Each rowConditions[i] = [a, b] demands that value a end up in a row strictly above value b, and each colConditions[j] = [a, b] demands that a end up in a column strictly to the left of b.
Build any k × k matrix containing each integer from 1 to k exactly once (every other cell holds 0) that satisfies all conditions, or return an empty matrix if the conditions are contradictory.
k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]][[0,0,1],[3,0,0],[0,2,0]]def build_matrix(k, row_conditions, col_conditions):
def topo_sort(conds):
adj = [[] for _ in range(k + 1)]
indeg = [0] * (k + 1)
for a, b in conds:
adj[a].append(b)
indeg[b] += 1
queue = [v for v in range(1, k + 1) if indeg[v] == 0]
order = []
while queue:
v = queue.pop(0)
order.append(v)
for nxt in adj[v]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
queue.append(nxt)
return order if len(order) == k else []
row_order = topo_sort(row_conditions)
col_order = topo_sort(col_conditions)
if not row_order or not col_order:
return []
row_idx = {v: i for i, v in enumerate(row_order)}
col_idx = {v: i for i, v in enumerate(col_order)}
matrix = [[0] * k for _ in range(k)]
for v in range(1, k + 1):
matrix[row_idx[v]][col_idx[v]] = v
return matrixfunction buildMatrix(k, rowConditions, colConditions) {
const topoSort = (conds) => {
const adj = Array.from({ length: k + 1 }, () => []);
const indeg = new Array(k + 1).fill(0);
for (const [a, b] of conds) { adj[a].push(b); indeg[b]++; }
const queue = [];
for (let v = 1; v <= k; v++) if (indeg[v] === 0) queue.push(v);
const order = [];
let head = 0;
while (head < queue.length) {
const v = queue[head++];
order.push(v);
for (const nxt of adj[v])
if (--indeg[nxt] === 0) queue.push(nxt);
}
return order.length === k ? order : [];
};
const rowOrder = topoSort(rowConditions);
const colOrder = topoSort(colConditions);
if (!rowOrder.length || !colOrder.length) return [];
const rowIdx = new Map(), colIdx = new Map();
rowOrder.forEach((v, i) => rowIdx.set(v, i));
colOrder.forEach((v, i) => colIdx.set(v, i));
const matrix = Array.from({ length: k }, () => new Array(k).fill(0));
for (let v = 1; v <= k; v++) matrix[rowIdx.get(v)][colIdx.get(v)] = v;
return matrix;
}public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
int[] rowOrder = topoSort(k, rowConditions);
int[] colOrder = topoSort(k, colConditions);
if (rowOrder.length == 0 || colOrder.length == 0) return new int[0][0];
int[] rowIdx = new int[k + 1], colIdx = new int[k + 1];
for (int i = 0; i < k; i++) rowIdx[rowOrder[i]] = i;
for (int i = 0; i < k; i++) colIdx[colOrder[i]] = i;
int[][] matrix = new int[k][k];
for (int v = 1; v <= k; v++) matrix[rowIdx[v]][colIdx[v]] = v;
return matrix;
}
int[] topoSort(int k, int[][] conds) {
List<List<Integer>> adj = new ArrayList<>();
for (int v = 0; v <= k; v++) adj.add(new ArrayList<>());
int[] indeg = new int[k + 1];
for (int[] c : conds) { adj.get(c[0]).add(c[1]); indeg[c[1]]++; }
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 1; v <= k; v++) if (indeg[v] == 0) queue.add(v);
int[] order = new int[k];
int n = 0;
while (!queue.isEmpty()) {
int v = queue.poll();
order[n++] = v;
for (int nxt : adj.get(v))
if (--indeg[nxt] == 0) queue.add(nxt);
}
return n == k ? order : new int[0];
}vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions,
vector<vector<int>>& colConditions) {
auto topoSort = [&](vector<vector<int>>& conds) {
vector<vector<int>> adj(k + 1);
vector<int> indeg(k + 1, 0), order;
for (auto& c : conds) { adj[c[0]].push_back(c[1]); indeg[c[1]]++; }
queue<int> q;
for (int v = 1; v <= k; v++) if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
for (int nxt : adj[v])
if (--indeg[nxt] == 0) q.push(nxt);
}
if ((int)order.size() != k) order.clear();
return order;
};
vector<int> rowOrder = topoSort(rowConditions);
vector<int> colOrder = topoSort(colConditions);
if (rowOrder.empty() || colOrder.empty()) return {};
vector<int> rowIdx(k + 1), colIdx(k + 1);
for (int i = 0; i < k; i++) rowIdx[rowOrder[i]] = i;
for (int i = 0; i < k; i++) colIdx[colOrder[i]] = i;
vector<vector<int>> matrix(k, vector<int>(k, 0));
for (int v = 1; v <= k; v++) matrix[rowIdx[v]][colIdx[v]] = v;
return matrix;
}Explanation
The key insight is that the row a value lands in and the column it lands in are completely independent. A row condition [a, b] only says "a's row index < b's row index" and never mentions columns; a column condition only constrains column indices. So the 2-D problem splits into two 1-D ordering problems.
Each ordering problem is exactly a topological sort. Treat every condition [a, b] as a directed edge a → b in a graph on the values 1..k. Kahn's algorithm computes the order: count each node's indegree, seed a queue with the indegree-0 nodes, and repeatedly pop a node, append it to the order, and decrement its neighbors' indegrees, enqueueing any that reach 0.
If the sort finishes with fewer than k values, the conditions contain a cycle (e.g. a above b above a) and no matrix can satisfy them, so we return an empty matrix. Otherwise the row order tells us each value's row rank and the col order its column rank, and we simply place value v at matrix[rowIdx[v]][colIdx[v]]. Since the ranks are permutations, every row and every column receives exactly one value, and the topological orders guarantee every condition holds.
For the default example, the row edges 1→2 and 3→2 give indegrees 0, 2, 0, so 1 and 3 seed the queue and the row order comes out [1, 3, 2]. The column edges 2→1 and 3→2 give indegrees 1, 1, 0, so only 3 starts the queue and the col order is [3, 2, 1]. Value 1 goes to (row 0, col 2), value 2 to (2, 1), and value 3 to (1, 0), producing [[0,0,1],[3,0,0],[0,2,0]].
With n total conditions, each topological sort runs in O(k + n), and writing the answer touches all k² cells, so the total time is O(k² + n). The adjacency lists and the output matrix dominate memory at O(k² + n).