This is a popular interview question because it tests the ability to decompose a complex 2D problem into two simpler 1D graph problems.

Brute Force Approach for Build a Matrix With Conditions

A naive approach attempts to place numbers $1$ through $k$ into the matrix grid by trying every possible permutation of placements until one satisfies all conditions. Alternatively, one might try to generate all permutations of the numbers for the rows and all permutations for the columns.

Pseudo-code for Naive Backtracking:

text
function solve(index, matrix):
    if index > k:
        if checkAllConditions(matrix): return matrix
        return null
    
    for r from 0 to k-1:
        for c from 0 to k-1:
            if matrix[r][c] is empty:
                matrix[r][c] = index
                result = solve(index + 1, matrix)
                if result is valid: return result
                matrix[r][c] = empty // backtrack
    return null

Time Complexity: The complexity is roughly $O((k^2)!)$ or $O(k!)$ depending on the specific permutation strategy. With $k \le 400$, $k!$ is astronomically large (far exceeding the number of atoms in the universe).

Why it fails: The constraints allow for $k$ up to 400. Any exponential or factorial solution will immediately result in a Time Limit Exceeded (TLE). We need a polynomial time solution, specifically one close to linear relative to the number of constraints.

Core Insight for Build a Matrix With Conditions

The critical insight for LeetCode 2392 is independence. The constraints affecting row placement are entirely independent of the constraints affecting column placement.

1. Decomposition: We can solve for the row indices of numbers $1 \dots k$ completely ignoring their column positions, and vice versa.
2. Graph Representation:
   • rowConditions can be viewed as a directed graph where an edge $u \to v$ means $u$ must appear in a row index strictly smaller than $v$.
   • colConditions forms a second, separate directed graph where $u \to v$ means $u$ must appear in a column index strictly smaller than $v$.
3. Topological Sort: A topological sort of the "row graph" gives us a valid sequence of numbers from top to bottom. If the sort returns [3, 1, 2], it means number 3 goes in row 0, number 1 in row 1, and number 2 in row 2. We apply the same logic to the "column graph".
4. Cycle Detection: If either graph contains a cycle (e.g., 1 is above 2, 2 is above 3, and 3 is above 1), a topological sort is impossible, and no valid matrix exists.

Visual Description: Imagine the numbers $1$ to $k$ as nodes in a graph. For the row conditions, draw a directed arrow from the "above" number to the "below" number. Kahn's algorithm visualizes this by identifying nodes with no incoming arrows (in-degree 0)—these are the candidates for the topmost available row. Once a number is placed, we remove it and its outgoing arrows, potentially freeing up new numbers to be placed in the next row. This process repeats layer by layer.

Algorithm Strategy: Graph BFS - Topological Sort (Kahn's Algorithm)

We will implement Kahn's Algorithm twice: once for rows and once for columns.

1. Graph Construction: For the given conditions (row or col), build an adjacency list and an in_degree array. The in_degree array tracks how many prerequisites each number has.
2. Queue Initialization: Push all numbers with an in_degree of 0 into a queue. These numbers have no dependencies and can be placed first.
3. Process Queue (BFS):
   • Pop a number u from the queue and add it to the result list.
   • Iterate through all neighbors v of u (where $u \to v$).
   • Decrement the in_degree of v.
   • If v's in_degree becomes 0, push v into the queue.
4. Validation: If the size of the result list is less than $k$, a cycle exists. Return an empty matrix immediately.
5. Matrix Assembly:
   • Map each number to its index in the row topological sort (its row coordinate).
   • Map each number to its index in the column topological sort (its column coordinate).
   • Initialize a $k \times k$ matrix with zeros.
   • Place each number $1 \dots k$ at its calculated (row, col) coordinate.

Execution Flow

Let's trace the logic with $k=3$, rowConditions=[[1,2], [3,2]], colConditions=[[2,1], [3,2]].

1. Solve Row Constraints:

   • Edges: $1 \to 2$, $3 \to 2$.
   • In-degrees: $\{1: 0, 2: 2, 3: 0\}$.
   • Queue initially: $[1, 3]$ (order in queue doesn't matter for validity).
   • Pop 1: Add to rowOrder. Decrement 2's degree (now 1).
   • Pop 3: Add to rowOrder. Decrement 2's degree (now 0). Push 2.
   • Pop 2: Add to rowOrder.
   • rowOrder: $[1, 3, 2]$ (Indices: 1 is at row 0, 3 at row 1, 2 at row 2).

2. Solve Column Constraints:

   • Edges: $2 \to 1$, $3 \to 2$.
   • In-degrees: $\{1: 1, 2: 1, 3: 0\}$.

3. Construct Matrix:

   • Number 1: Row index 0 (from rowOrder), Col index 2 (from colOrder).
   • Number 2: Row index 2, Col index 1.
   • Number 3: Row index 1, Col index 0.
   • Result:

     text
     0 0 1
     3 0 0
     0 2 0

   (Note: This output differs slightly from the example explanation because topological sort order for independent nodes is not unique, but both are valid).

Proof of Correctness

The algorithm relies on the property of Topological Sort. A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge $u \to v$, $u$ comes before $v$ in the ordering.

By using the index in the topological sort as the matrix coordinate:

1. If rowConditions specify $u$ above $v$, the graph has edge $u \to v$. The sort places $u$ before $v$. Thus, rowIndex[u] < rowIndex[v]. The condition is satisfied.
2. The same logic applies to colConditions.
3. Since we use Kahn's algorithm, we naturally detect cycles (if the result length $< k$). If a cycle exists, no linear ordering satisfies the conditions, so we correctly return empty.

Reference Implementation

C++ Solution for LeetCode 2392

cpp
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
    // Helper function to perform Kahn's Algorithm (Topological Sort)
    vector<int> topologicalSort(int k, vector<vector<int>>& conditions) {
        vector<vector<int>> adj(k + 1);
        vector<int> inDegree(k + 1, 0);
        
        // Build Graph
        for (const auto& cond : conditions) {
            int u = cond[0];
            int v = cond[1];
            adj[u].push_back(v);
            inDegree[v]++;
        }
        
        // Initialize Queue with nodes having 0 in-degree
        queue<int> q;
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> order;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            
            for (int v : adj[u]) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        // If we didn't visit all k nodes, there's a cycle
        if (order.size() != k) return {};
        return order;
    }

    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> rowOrder = topologicalSort(k, rowConditions);
        vector<int> colOrder = topologicalSort(k, colConditions);
        
        // If either sort failed due to a cycle
        if (rowOrder.empty() || colOrder.empty()) return {};
        
        // Map value -> index
        vector<int> rowIndex(k + 1), colIndex(k + 1);
        for (int i = 0; i < k; i++) {
            rowIndex[rowOrder[i]] = i;
            colIndex[colOrder[i]] = i;
        }
        
        // Build result matrix
        vector<vector<int>> matrix(k, vector<int>(k, 0));
        for (int i = 1; i <= k; i++) {
            matrix[rowIndex[i]][colIndex[i]] = i;
        }
        
        return matrix;
    }
};

Java Solution for LeetCode 2392

java
import java.util.*;

class Solution {
    // Helper function for Kahn's Algorithm
    private List<Integer> topologicalSort(int k, int[][] conditions) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= k; i++) {
            adj.add(new ArrayList<>());
        }
        int[] inDegree = new int[k + 1];
        
        for (int[] cond : conditions) {
            int u = cond[0];
            int v = cond[1];
            adj.get(u).add(v);
            inDegree[v]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) {
                q.add(i);
            }
        }
        
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            
            for (int v : adj.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.add(v);
                }
            }
        }
        
        if (order.size() != k) return new ArrayList<>();
        return order;
    }

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        List<Integer> rowOrder = topologicalSort(k, rowConditions);
        List<Integer> colOrder = topologicalSort(k, colConditions);
        
        if (rowOrder.isEmpty() || colOrder.isEmpty()) {
            return new int[0][0];
        }
        
        // Map value to its determined index
        int[] rowIndex = new int[k + 1];
        int[] colIndex = new int[k + 1];
        
        for (int i = 0; i < k; i++) {
            rowIndex[rowOrder.get(i)] = i;
            colIndex[colOrder.get(i)] = i;
        }
        
        int[][] matrix = new int[k][k];
        for (int i = 1; i <= k; i++) {
            matrix[rowIndex[i]][colIndex[i]] = i;
        }
        
        return matrix;
    }
}

Python Solution for LeetCode 2392

python
from collections import deque, defaultdict

class Solution:
    def buildMatrix(self, k: int, rowConditions: list[list[int]], colConditions: list[list[int]]) -> list[list[int]]:
        
        def topological_sort(conditions):
            adj = defaultdict(list)
            in_degree = {i: 0 for i in range(1, k + 1)}
            
            for u, v in conditions:
                adj[u].append(v)
                in_degree[v] += 1
            
            queue = deque([node for node in in_degree if in_degree[node] == 0])
            order = []
            
            while queue:
                u = queue.popleft()
                order.append(u)
                
                for v in adj[u]:
                    in_degree[v] -= 1
                    if in_degree[v] == 0:
                        queue.append(v)
            
            # Check for cycle
            if len(order) != k:
                return []
            return order

        row_order = topological_sort(rowConditions)
        col_order = topological_sort(colConditions)
        
        if not row_order or not col_order:
            return []
        
        # Map values to their indices
        row_pos = {val: i for i, val in enumerate(row_order)}
        col_pos = {val: i for i, val in enumerate(col_order)}
        
        matrix = [[0] * k for _ in range(k)]
        
        for num in range(1, k + 1):
            r, c = row_pos[num], col_pos[num]
            matrix[r][c] = num
            
        return matrix