Build a Matrix With Conditions

Hard · Graphs · Explanation and code example

Topological Sort (Kahn's Algorithm)

How it works

This approach solves the same problem using Kahn's algorithm (BFS-based topological sort) instead of DFS. The key insight remains the same: we need valid orderings for both rows and columns. Kahn's algorithm processes nodes with zero incoming edges first, which naturally produces a valid topological order when no cycle exists.

If we process fewer than k nodes, it means there's a cycle in the graph and no valid ordering is possible.

Steps

  1. For each condition set (row and column), build an adjacency list and compute in-degrees for all nodes.
  2. Initialize a queue with all nodes that have zero in-degree.
  3. Process nodes from the queue:
    • Add the current node to the order.
    • Decrease the in-degree of all neighbors.
    • Add neighbors with zero in-degree to the queue.
  4. If the order contains fewer than k nodes, a cycle exists; return empty matrix.
  5. Create index mappings from the row and column orderings.
  6. Place each number at its determined (row, column) position in the matrix.
  7. Return the matrix.

Complexity

  • Time complexity: O(k ^ 2 + n + m)
  • Space complexity:
    • O(k + n + m) extra space.
    • O(k ^ 2) space for the output matrix.

Where n is the size of the array rowConditions, m is the size of the array colConditions, and k is the size of the output matrix.

Things to watch for

Treating Row and Column Conditions as One Graph

Row conditions and column conditions must be processed as two separate, independent graphs. Combining them into a single graph leads to incorrect cycle detection and wrong orderings since row ordering has no relation to column ordering.

Not Detecting Cycles Properly in DFS

When using DFS for topological sort, you need both a visited set (permanently processed nodes) and a path set (nodes in current recursion stack). Using only one set fails to detect back edges that indicate cycles.

Forgetting to Include Nodes Without Edges

Numbers from 1 to k that don't appear in any condition still need positions in the matrix. The topological sort must iterate over all values 1 to k, not just those present in the edge list.

Off-by-One Errors with 1-Indexed Values

The values are 1 to k (1-indexed) but arrays are typically 0-indexed. When building adjacency lists or index mappings, mixing these up causes index out of bounds errors or incorrect placements.

Python code example

from typing import List
from collections import deque

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo_sort(edges):
            indegree = [0] * (k + 1)
            adj = [[] for _ in range(k + 1)]
            for u, v in edges:
                adj[u].append(v)
                indegree[v] += 1

            order = []
            q = deque()
            for i in range(1, k + 1):
                if not indegree[i]:
                    q.append(i)

            while q:
                node = q.popleft()
                order.append(node)
                for nei in adj[node]:
                    indegree[nei] -= 1
                    if not indegree[nei]:
                        q.append(nei)

            return order

        row_order = topo_sort(rowConditions)
        if len(row_order) != k: return []

        col_order = topo_sort(colConditions)
        if len(col_order) != k: return []

        res = [[0] * k for _ in range(k)]
        colIndex = [0] * (k + 1)
        for i in range(k):
            colIndex[col_order[i]] = i

        for i in range(k):
            res[i][colIndex[row_order[i]]] = row_order[i]
        return res

C++ code example

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> rowOrder = topoSort(k, rowConditions);
        if (rowOrder.size() != k) return {};

        vector<int> colOrder = topoSort(k, colConditions);
        if (colOrder.size() != k) return {};

        vector<vector<int>> res(k, vector<int>(k, 0));
        vector<int> colIndex(k + 1);
        for (int i = 0; i < k; i++) {
            colIndex[colOrder[i]] = i;
        }
        for (int i = 0; i < k; i++) {
            res[i][colIndex[rowOrder[i]]] = rowOrder[i];
        }
        return res;
    }

private:
    vector<int> topoSort(int k, vector<vector<int>>& edges) {
        vector<int> indegree(k + 1, 0);
        vector<vector<int>> adj(k + 1);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            indegree[edge[1]]++;
        }

        queue<int> q;
        vector<int> order;
        for (int i = 1; i <= k; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            order.push_back(node);

            for (int nei : adj[node]) {
                indegree[nei]--;
                if (indegree[nei] == 0) {
                    q.push(nei);
                }
            }
        }

        if (order.size() != k) return {};
        return order;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations