Build a Matrix with Conditions

Difficulty: Hard Source: NeetCode

Problem

You are given a positive integer k. You are also given:

• a 2D integer array rowConditions of size m with each rowConditions[i] = [abovei, belowi], which means that row of number abovei should appear above the row of number belowi.
• a 2D integer array colConditions of size n with each colConditions[i] = [lefti, righti], which means that column of number lefti should appear to the left of the column of number righti.

The numbers 1 through k must appear in the matrix exactly once. Return any matrix of size k x k satisfying both sets of conditions, or return an empty 2D array if it is impossible.

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]] (or any valid arrangement)

Example 2: Input: k=3, rowConditions=[[1,2],[2,3],[3,1],[2,3]], colConditions=[[2,1]] Output: [] (cycle in row conditions)

Constraints:

• 2 <= k <= 400
• 1 <= rowConditions.length, colConditions.length <= 10^4
• All numbers in conditions are in [1, k]

Prerequisites

Before attempting this problem, you should be comfortable with:

• Topological Sort — ordering nodes with dependency constraints
• Cycle Detection — recognizing when constraints are contradictory
• Graph Building — translating constraints into directed edges

1. Brute Force (Try All Permutations)

Intuition

Generate all permutations of 1..k, and for each permutation, check if the row and column orderings satisfy all conditions. Return a matrix if found. This works for tiny inputs but is O(k! * conditions) — completely impractical for k > 8.

We skip the implementation here since Kahn’s topological sort is both correct and efficient. This section just motivates why topological sort is the right tool.

2. Topological Sort (Kahn’s BFS)

Intuition

The row conditions say “number A must be in a row above number B” — this is exactly a topological ordering constraint. Same for columns. So we need to:

1. Find a valid topological ordering of numbers 1..k for row positions.
2. Find a valid topological ordering of numbers 1..k for column positions.
3. Place each number at (row_order[num], col_order[num]) in the k×k matrix.

If either topological sort finds a cycle, return [].

Algorithm

1. Build directed graphs for rows and columns from the respective conditions.
2. Run Kahn’s topological sort on each graph.
3. If either sort doesn’t include all k nodes (cycle detected), return [].
4. Create a row_pos and col_pos mapping: row_pos[num] = its position in row order.
5. Build the k×k zero matrix. For each number 1..k, set matrix[row_pos[num]][col_pos[num]] = num.
6. Return the matrix.

Solution

from collections import defaultdict, deque

def buildMatrix(k, rowConditions, colConditions):
    def topo_sort(conditions):
        graph = defaultdict(list)
        in_degree = {i: 0 for i in range(1, k + 1)}

        for u, v in conditions:
            graph[u].append(v)
            in_degree[v] += 1

        queue = deque([node for node in in_degree if in_degree[node] == 0])
        order = []

        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        return order if len(order) == k else []  # empty = cycle detected

    row_order = topo_sort(rowConditions)
    col_order = topo_sort(colConditions)

    if not row_order or not col_order:
        return []

    # Map each number to its position in the ordering
    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


k1 = 3
rc1 = [[1,2],[3,2]]
cc1 = [[2,1],[3,2]]
result = buildMatrix(k1, rc1, cc1)
for row in result:
    print(row)
print()

# Cycle case
k2 = 3
rc2 = [[1,2],[2,3],[3,1]]
cc2 = [[2,1]]
print(buildMatrix(k2, rc2, cc2))  # []

Complexity

• Time: O(k + R + C) where R = row conditions, C = col conditions
• Space: O(k + R + C) — graphs and ordering arrays

Common Pitfalls

Forgetting that all k numbers must appear even if they have no conditions. Initialize in_degree for all numbers from 1 to k, not just those mentioned in conditions. Otherwise, isolated nodes won’t be included in the topological order.

Checking len(order) == k for cycle detection. If there’s a cycle, Kahn’s BFS will stall before processing all nodes. The result length will be less than k — that’s your cycle indicator.

Confusing position with the number itself. row_order[i] is the number that goes in row i. You need the inverse: row_pos[num] = i tells you which row number num belongs to. Build the inverse mapping before constructing the matrix.