title: Build a Matrix With Conditions
slug: build-a-matrix-with-conditions
difficulty: hard
leetcode_id: 2392
leetcode_url: https://leetcode.com/problems/build-a-matrix-with-conditions/
categories:
  - arrays
  - graphs
patterns:
  - slug: topological-sort
    is_optimal: true

function_signature: "def build_matrix(k: int, row_conditions: list[list[int]], col_conditions: list[list[int]]) -> list[list[int]]:"

test_cases:
  visible:
    - input: { k: 3, row_conditions: [[1, 2], [3, 2]], col_conditions: [[2, 1], [3, 2]] }
      expected: [[3, 0, 0], [0, 0, 1], [0, 2, 0]]
    - input: { k: 3, row_conditions: [[1, 2], [2, 3], [3, 1], [2, 3]], col_conditions: [[2, 1]] }
      expected: []
  hidden:
    - input: { k: 2, row_conditions: [[1, 2]], col_conditions: [[1, 2]] }
      expected: [[1, 0], [0, 2]]
    - input: { k: 2, row_conditions: [[1, 2]], col_conditions: [[2, 1]] }
      expected: [[0, 1], [2, 0]]
    - input: { k: 2, row_conditions: [[1, 2], [2, 1]], col_conditions: [[1, 2]] }
      expected: []

description: |
  You are given a **positive** integer `k`. You are also given:

  - a 2D integer array `rowConditions` of size `n` where `rowConditions[i] = [above_i, below_i]`, and
  - a 2D integer array `colConditions` of size `m` where `colConditions[i] = [left_i, right_i]`.

  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 `above_i` should appear in a **row** that is strictly **above** the row at which the number `below_i` appears for all `i` from `0` to `n - 1`.
  - The number `left_i` should appear in a **column** that is strictly **left** of the column at which the number `right_i` appears for all `i` from `0` to `m - 1`.

  Return *any matrix that satisfies the conditions*. If no answer exists, return an empty matrix.

constraints: |
  - `2 <= k <= 400`
  - `1 <= rowConditions.length, colConditions.length <= 10^4`
  - `rowConditions[i].length == colConditions[i].length == 2`
  - `1 <= above_i, below_i, left_i, right_i <= k`
  - `above_i != below_i`
  - `left_i != right_i`

examples:
  - input: "k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]"
    output: "[[3,0,0],[0,0,1],[0,2,0]]"
    explanation: "Number 1 is in row 1 and number 2 is in row 2, so 1 is above 2. Number 3 is in row 0 and number 2 is in row 2, so 3 is above 2. For columns: 2 is in column 1 and 1 is in column 2, so 2 is left of 1. Number 3 is in column 0 and 2 is in column 1, so 3 is left of 2. Note that multiple valid answers exist."
  - 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 condition needs 3 to be above 1. No matrix can satisfy all conditions, so we return an empty matrix."

explanation:
  intuition: |
    Imagine you're arranging people in a grid for a photo, but with specific ordering rules: "Person A must be in a row above Person B" and "Person C must be in a column left of Person D."

    The key insight is that **row positions and column positions are independent problems**. Where a number sits vertically (its row) has nothing to do with where it sits horizontally (its column). This means we can solve for row ordering and column ordering separately, then combine them.

    Each ordering problem is actually a **topological sort**. The condition `[above, below]` means `above → below` is a directed edge — "above must come before below." If we can find a valid ordering (no cycles), we get a sequence like `[3, 1, 2]` meaning "3 goes in row 0, 1 in row 1, 2 in row 2."

    Think of it like course prerequisites: if Course A requires Course B, you must take B first. If there's a circular dependency (A needs B, B needs C, C needs A), it's impossible — that's a cycle. Similarly, if our row or column conditions form a cycle, no valid matrix exists.

    Once we have valid row and column orderings, placing numbers is straightforward: each number's position is `(row_order[num], col_order[num])`.

  approach: |
    We solve this by performing **two independent topological sorts** — one for row constraints and one for column constraints.

    **Step 1: Build adjacency lists for both dimensions**

    - Create a graph for row conditions where edge `(a, b)` means `a` must be in a row above `b`
    - Create a separate graph for column conditions where edge `(a, b)` means `a` must be in a column left of `b`
    - Track in-degrees (number of incoming edges) for each node in both graphs

    &nbsp;

    **Step 2: Perform topological sort using Kahn's algorithm (BFS)**

    - Initialise a queue with all nodes having in-degree `0` (no prerequisites)
    - Process nodes one by one: add to result, then reduce in-degree of neighbours
    - When a neighbour's in-degree becomes `0`, add it to the queue
    - If the result doesn't contain all `k` numbers, a cycle exists — return empty matrix

    &nbsp;

    **Step 3: Create position mappings from topological orders**

    - Convert the row order `[3, 1, 2]` to a mapping: `{3: 0, 1: 1, 2: 2}` (number → row index)
    - Do the same for column order
    - Numbers not in any condition can be placed in any remaining position

    &nbsp;

    **Step 4: Construct the matrix**

    - Create a `k x k` matrix filled with zeros
    - For each number from `1` to `k`, place it at position `(row_pos[num], col_pos[num])`
    - Return the completed matrix

  common_pitfalls:
    - title: Forgetting Cycle Detection
      description: |
        The most critical part is detecting when no valid ordering exists. A cycle in row conditions like `[1,2], [2,3], [3,1]` makes it impossible: 1 must be above 2, 2 above 3, but 3 above 1 creates a contradiction.

        If your topological sort doesn't return exactly `k` elements, there's a cycle. Always check the length of your result before proceeding.
      wrong_approach: "Assuming topological sort always succeeds"
      correct_approach: "Check if topological sort returns exactly k elements; if not, return []"

    - title: Treating Row and Column as One Problem
      description: |
        It might seem like you need to simultaneously satisfy both row and column constraints. This makes the problem feel impossibly complex.

        The insight is that row position and column position are **completely independent**. A number's row is determined only by row conditions; its column only by column conditions. Solve them separately, then combine.
      wrong_approach: "Trying to solve both dimensions together"
      correct_approach: "Separate topological sorts for rows and columns"

    - title: Handling Numbers Without Constraints
      description: |
        Not every number from `1` to `k` appears in the conditions. For example, if `k = 5` but conditions only mention numbers `1, 2, 3`, then `4` and `5` have no constraints.

        These unconstrained numbers have in-degree `0` from the start and can be placed anywhere in the ordering. Make sure your topological sort processes all `k` numbers, not just those in the conditions.
      wrong_approach: "Only processing numbers mentioned in conditions"
      correct_approach: "Initialise in-degree for all numbers 1 to k, starting unconstrained ones with 0"

    - title: Confusing Edge Direction
      description: |
        The condition `[above, below]` means `above` must come **before** `below` in the ordering. The directed edge goes `above → below`, not the reverse.

        Getting this backwards will produce invalid orderings where constraints are violated.
      wrong_approach: "Edge from below to above"
      correct_approach: "Edge from above to below (prerequisite points to dependent)"

  key_takeaways:
    - "**Decomposition**: When constraints affect independent dimensions, solve each separately and combine"
    - "**Topological sort for ordering**: Whenever you have \"A must come before B\" constraints, think topological sort"
    - "**Cycle detection is essential**: A cycle in directed constraints means no valid solution exists"
    - "**Kahn's algorithm (BFS)**: Process nodes with no remaining prerequisites; if not all nodes processed, there's a cycle"

  time_complexity: "O(k + n + m). Building graphs takes O(n + m) for the conditions. Topological sort visits each node once and each edge once, giving O(k + n + m). Matrix construction is O(k^2) but dominated by k being at most 400."
  space_complexity: "O(k + n + m). We store adjacency lists with up to n + m edges total, in-degree arrays of size k, and the k × k output matrix."

solutions:
  - approach_name: Topological Sort (Kahn's Algorithm)
    is_optimal: true
    code: |
      from collections import deque

      def build_matrix(k: int, row_conditions: list[list[int]], col_conditions: list[list[int]]) -> list[list[int]]:
          def topological_sort(conditions: list[list[int]]) -> list[int]:
              # Build adjacency list and in-degree count
              graph = [[] for _ in range(k + 1)]
              in_degree = [0] * (k + 1)

              for a, b in conditions:
                  graph[a].append(b)  # a must come before b
                  in_degree[b] += 1

              # Start with all nodes that have no prerequisites
              queue = deque()
              for node in range(1, k + 1):
                  if in_degree[node] == 0:
                      queue.append(node)

              order = []
              while queue:
                  node = queue.popleft()
                  order.append(node)

                  # Process all neighbours
                  for neighbour in graph[node]:
                      in_degree[neighbour] -= 1
                      if in_degree[neighbour] == 0:
                          queue.append(neighbour)

              # If we didn't process all nodes, there's a cycle
              return order if len(order) == k else []

          # Get valid orderings for rows and columns
          row_order = topological_sort(row_conditions)
          col_order = topological_sort(col_conditions)

          # If either has a cycle, no valid matrix exists
          if not row_order or not col_order:
              return []

          # Convert orders to position mappings
          row_pos = {num: idx for idx, num in enumerate(row_order)}
          col_pos = {num: idx for idx, num in enumerate(col_order)}

          # Build the matrix
          matrix = [[0] * k for _ in range(k)]
          for num in range(1, k + 1):
              matrix[row_pos[num]][col_pos[num]] = num

          return matrix
    explanation: |
      **Time Complexity:** O(k + n + m) — We process each node and edge once in topological sort, plus O(k^2) for matrix construction.

      **Space Complexity:** O(k + n + m) — Adjacency lists, in-degree arrays, and the output matrix.

      We perform two independent topological sorts using Kahn's algorithm (BFS-based). Each sort produces an ordering where all "must come before" constraints are satisfied. If either sort fails to include all k numbers, a cycle exists and we return an empty matrix. Otherwise, we use the orderings to determine each number's row and column position.

  - approach_name: Topological Sort (DFS)
    is_optimal: false
    code: |
      def build_matrix(k: int, row_conditions: list[list[int]], col_conditions: list[list[int]]) -> list[list[int]]:
          def topological_sort_dfs(conditions: list[list[int]]) -> list[int]:
              # Build adjacency list
              graph = [[] for _ in range(k + 1)]
              for a, b in conditions:
                  graph[a].append(b)

              # 0 = unvisited, 1 = visiting (in current path), 2 = visited
              state = [0] * (k + 1)
              order = []
              has_cycle = False

              def dfs(node: int) -> None:
                  nonlocal has_cycle
                  if has_cycle or state[node] == 2:
                      return
                  if state[node] == 1:  # Back edge = cycle
                      has_cycle = True
                      return

                  state[node] = 1  # Mark as visiting
                  for neighbour in graph[node]:
                      dfs(neighbour)
                  state[node] = 2  # Mark as visited
                  order.append(node)  # Add to order after all descendants

              # Run DFS from all nodes
              for node in range(1, k + 1):
                  if state[node] == 0:
                      dfs(node)
                  if has_cycle:
                      return []

              # Reverse to get correct topological order
              return order[::-1]

          row_order = topological_sort_dfs(row_conditions)
          col_order = topological_sort_dfs(col_conditions)

          if not row_order or not col_order:
              return []

          row_pos = {num: idx for idx, num in enumerate(row_order)}
          col_pos = {num: idx for idx, num in enumerate(col_order)}

          matrix = [[0] * k for _ in range(k)]
          for num in range(1, k + 1):
              matrix[row_pos[num]][col_pos[num]] = num

          return matrix
    explanation: |
      **Time Complexity:** O(k + n + m) — Same as BFS approach, visiting each node and edge once.

      **Space Complexity:** O(k + n + m) — Plus O(k) recursion stack depth in the worst case.

      This DFS-based approach uses three states to detect cycles: unvisited, visiting (in current DFS path), and visited. A back edge to a "visiting" node indicates a cycle. Nodes are added to the order after all their descendants are processed, then reversed to get the correct topological order. While equally correct, the BFS approach is often preferred as it avoids recursion depth issues.
