NeetCode #654LC-2392HardAdvanced GraphsNC 250
← Back to All Problems#654 · #2392 · Build a Matrix With Conditions(给定条件下构造矩阵)
📌 Problem Statement & Constraints
You are given a positive integer
k, rowConditions where rowConditions[i] = [above, below] means the value above must be in a row strictly above below, and similarly colConditions. Return a k x k matrix containing 1..k satisfying both, or an empty matrix if impossible. Constraints: 2 <= k <= 400, 1 <= rowConditions.length, colConditions.length <= 10^4.💡 Core Algorithmic Approaches
- Each constraint set is a partial order, so a topological sort gives a valid linear arrangement.
- Run the topological sort separately for the rows and the columns.
- If either has a cycle (fewer than
knodes ordered), return an empty matrix. - Place the value
vat(row_position[v], col_position[v]).
💻 Benchmark Python3 Implementation
class Solution:
def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
from collections import defaultdict, deque
def topo(conds: List[List[int]]):
g = defaultdict(list)
indeg = [0] * (k + 1)
for a, b in conds:
g[a].append(b)
indeg[b] += 1
q = deque(i for i in range(1, k + 1) if indeg[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nxt in g[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return order if len(order) == k else None # None -> cycle
row_order = topo(rowConditions)
col_order = topo(colConditions)
if row_order is None or col_order is None:
return []
row_pos = {v: i for i, v in enumerate(row_order)}
col_pos = {v: i for i, v in enumerate(col_order)}
res = [[0] * k for _ in range(k)]
for v in range(1, k + 1):
res[row_pos[v]][col_pos[v]] = v
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(k + E): one topological sort per constraint set.
💾 Space Complexity
O(k + E) for the graphs.
⚠️ Interview Pitfalls & Follow-ups
- Running one topological sort for both constraints: the row and column orders are independent.
- Forgetting the cycle check: a cyclic constraint set makes the arrangement impossible.
- Placing values by the constraint order rather than the position: the positions come from the topological order.
- Assuming the values are 0-indexed: they are
1..k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.