⚡Flashcard Drill➔
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

  1. Each constraint set is a partial order, so a topological sort gives a valid linear arrangement.
  2. Run the topological sort separately for the rows and the columns.
  3. If either has a cycle (fewer than k nodes ordered), return an empty matrix.
  4. Place the value v at (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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems