Build a Matrix With Conditions

🎯

Build a Matrix With Conditions

hardGRAPHAmazonGoogle

Imagine you are tasked with arranging students in a classroom seating chart based on two sets of constraints: one for rows and one for columns. How do you ensure all conditions are met simultaneously?

💡 This problem involves understanding how to order elements based on dependency constraints in two separate dimensions simultaneously. Beginners often struggle because it requires combining two topological sorts and then mapping the results into a matrix, which is more complex than a single ordering.

📋

Problem Statement

Given two integers n and two lists of conditions, rowConditions and colConditions, each containing pairs [a, b] indicating that a must come before b in the row or column ordering respectively, construct an n x n matrix with integers from 1 to n such that the row and column orderings satisfy the given conditions. If no such matrix exists, return an empty matrix.

1 ≤ n ≤ 10^51 ≤ number of conditions in rowConditions, colConditions ≤ 10^51 ≤ a, b ≤ na != b

💡

Example

Input"n = 3, rowConditions = [[1,2],[2,3]], colConditions = [[2,1],[3,2]]"

Output[[3,0,0],[0,2,0],[0,0,1]]

Row order is 1->2->3, column order is 3->2->1, so 1 is at row 0 col 2, 2 at row 1 col 1, 3 at row 2 col 0.

• No conditions given → any permutation matrix is valid
• Conflicting conditions in rowConditions → return empty matrix
• Conflicting conditions in colConditions → return empty matrix
• Single element n=1 → matrix is [[1]]

⚠️

Common Mistakes

Not detecting cycles properly

Returns incorrect matrix or infinite loop

✅ Implement cycle detection in topological sort and return empty if cycle found

Mixing up row and column orderings

Matrix does not satisfy one set of conditions

✅ Maintain separate graphs and orders for rows and columns

Using recursion without handling large input constraints

Stack overflow or timeout on large inputs

✅ Use iterative BFS (Kahn's algorithm) for topological sort

Incorrectly mapping positions after topological sort

Numbers placed in wrong matrix cells

✅ Map each number to its index in the topological order before placing

Not handling isolated nodes (no incoming or outgoing edges)

Missing nodes in final matrix or incorrect ordering

✅ Include all nodes in topological sort initialization

🧠

Brute Force (Cycle Detection with DFS + Naive Positioning)

💡 Starting with brute force helps understand the problem's core: verifying if the given conditions form valid orderings and then trying to place elements accordingly, even if inefficient.

Intuition

Try to build the orderings by checking for cycles using DFS in both row and column conditions. If no cycles, assign positions based on the order found. This approach is straightforward but not optimized for large inputs.

Algorithm

1. Build adjacency lists for rowConditions and colConditions.
2. Use DFS to detect cycles and generate topological order for rows and columns.
3. If a cycle is detected in either, return empty matrix.
4. Assign each number a row and column index based on the topological orderings.
5. Construct the matrix placing each number at its assigned row and column.

💡 The challenge is to understand how to detect cycles and produce a valid ordering, then map that ordering to matrix positions.

</>

Code

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def build_graph(conditions, n):
    graph = defaultdict(list)
    for u, v in conditions:
        graph[u].append(v)
    return graph

def dfs(node, graph, visited, stack):
    if visited[node] == 1:  # visiting
        return False
    if visited[node] == 2:  # visited
        return True
    visited[node] = 1
    for nei in graph[node]:
        if not dfs(nei, graph, visited, stack):
            return False
    visited[node] = 2
    stack.append(node)
    return True

def topological_sort(conditions, n):
    graph = build_graph(conditions, n)
    visited = [0] * (n + 1)
    stack = []
    for node in range(1, n + 1):
        if visited[node] == 0:
            if not dfs(node, graph, visited, stack):
                return []
    stack.reverse()
    return stack

def buildMatrix(n, rowConditions, colConditions):
    row_order = topological_sort(rowConditions, n)
    if not row_order:
        return []
    col_order = topological_sort(colConditions, n)
    if not col_order:
        return []
    pos_in_row = {num: i for i, num in enumerate(row_order)}
    pos_in_col = {num: i for i, num in enumerate(col_order)}
    matrix = [[0] * n for _ in range(n)]
    for num in range(1, n + 1):
        r = pos_in_row[num]
        c = pos_in_col[num]
        matrix[r][c] = num
    return matrix

# Driver code
if __name__ == '__main__':
    n = 3
    rowConditions = [[1,2],[2,3]]
    colConditions = [[2,1],[3,2]]
    result = buildMatrix(n, rowConditions, colConditions)
    for row in result:
        print(row)

Line Notes

def build_graph(conditions, n):Helper to create adjacency list from conditions to represent dependencies

for u, v in conditions:Add directed edges from u to v indicating u must come before v

def dfs(node, graph, visited, stack):DFS function to detect cycles and build topological order

if visited[node] == 1:If node is currently being visited, a cycle is detected

stack.append(node)Add node to stack after visiting all descendants to build order

def topological_sort(conditions, n):Perform topological sort or return empty if cycle detected

for node in range(1, n + 1):Visit all nodes including isolated ones to ensure full ordering

row_order = topological_sort(rowConditions, n)Get row ordering or empty if invalid due to cycle

pos_in_row = {num: i for i, num in enumerate(row_order)}Map each number to its row index for placement

matrix = [[0] * n for _ in range(n)]Initialize empty n x n matrix with zeros

matrix[r][c] = numPlace number at its assigned row and column position in matrix

import java.util.*;

public class BuildMatrix {
    private static Map<Integer, List<Integer>> buildGraph(int[][] conditions, int n) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) graph.put(i, new ArrayList<>());
        for (int[] cond : conditions) {
            graph.get(cond[0]).add(cond[1]);
        }
        return graph;
    }

    private static boolean dfs(int node, Map<Integer, List<Integer>> graph, int[] visited, List<Integer> stack) {
        if (visited[node] == 1) return false; // cycle
        if (visited[node] == 2) return true;  // visited
        visited[node] = 1;
        for (int nei : graph.get(node)) {
            if (!dfs(nei, graph, visited, stack)) return false;
        }
        visited[node] = 2;
        stack.add(node);
        return true;
    }

    private static List<Integer> topologicalSort(int[][] conditions, int n) {
        Map<Integer, List<Integer>> graph = buildGraph(conditions, n);
        int[] visited = new int[n + 1];
        List<Integer> stack = new ArrayList<>();
        for (int node = 1; node <= n; node++) {
            if (visited[node] == 0) {
                if (!dfs(node, graph, visited, stack)) return new ArrayList<>();
            }
        }
        Collections.reverse(stack);
        return stack;
    }

    public static int[][] buildMatrix(int n, int[][] rowConditions, int[][] colConditions) {
        List<Integer> rowOrder = topologicalSort(rowConditions, n);
        if (rowOrder.isEmpty()) return new int[0][0];
        List<Integer> colOrder = topologicalSort(colConditions, n);
        if (colOrder.isEmpty()) return new int[0][0];
        int[] posInRow = new int[n + 1];
        int[] posInCol = new int[n + 1];
        for (int i = 0; i < n; i++) {
            posInRow[rowOrder.get(i)] = i;
            posInCol[colOrder.get(i)] = i;
        }
        int[][] matrix = new int[n][n];
        for (int num = 1; num <= n; num++) {
            matrix[posInRow[num]][posInCol[num]] = num;
        }
        return matrix;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] rowConditions = {{1,2},{2,3}};
        int[][] colConditions = {{2,1},{3,2}};
        int[][] result = buildMatrix(n, rowConditions, colConditions);
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

private static Map<Integer, List<Integer>> buildGraph(int[][] conditions, int n)Build adjacency list from conditions to represent dependencies

for (int[] cond : conditions)Add directed edges from cond[0] to cond[1]

private static boolean dfs(int node, Map<Integer, List<Integer>> graph, int[] visited, List<Integer> stack)DFS to detect cycles and build topological order

if (visited[node] == 1) return false;Cycle detected if node is currently being visited

stack.add(node);Add node after visiting all descendants to build order

private static List<Integer> topologicalSort(int[][] conditions, int n)Perform topological sort or return empty list if cycle detected

for (int node = 1; node <= n; node++)Visit all nodes including isolated ones

List<Integer> rowOrder = topologicalSort(rowConditions, n);Get row order or empty if invalid

int[] posInRow = new int[n + 1];Map each number to its row index

matrix[posInRow[num]][posInCol[num]] = num;Place number in matrix at assigned position

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> buildGraph(vector<vector<int>>& conditions, int n) {
    unordered_map<int, vector<int>> graph;
    for (int i = 1; i <= n; i++) graph[i] = {};
    for (auto& cond : conditions) {
        graph[cond[0]].push_back(cond[1]);
    }
    return graph;
}

bool dfs(int node, unordered_map<int, vector<int>>& graph, vector<int>& visited, vector<int>& stack) {
    if (visited[node] == 1) return false; // cycle
    if (visited[node] == 2) return true;  // visited
    visited[node] = 1;
    for (int nei : graph[node]) {
        if (!dfs(nei, graph, visited, stack)) return false;
    }
    visited[node] = 2;
    stack.push_back(node);
    return true;
}

vector<int> topologicalSort(vector<vector<int>>& conditions, int n) {
    auto graph = buildGraph(conditions, n);
    vector<int> visited(n + 1, 0);
    vector<int> stack;
    for (int node = 1; node <= n; node++) {
        if (visited[node] == 0) {
            if (!dfs(node, graph, visited, stack)) return {};
        }
    }
    reverse(stack.begin(), stack.end());
    return stack;
}

vector<vector<int>> buildMatrix(int n, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
    vector<int> rowOrder = topologicalSort(rowConditions, n);
    if (rowOrder.empty()) return {};
    vector<int> colOrder = topologicalSort(colConditions, n);
    if (colOrder.empty()) return {};
    vector<int> posInRow(n + 1), posInCol(n + 1);
    for (int i = 0; i < n; i++) {
        posInRow[rowOrder[i]] = i;
        posInCol[colOrder[i]] = i;
    }
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int num = 1; num <= n; num++) {
        matrix[posInRow[num]][posInCol[num]] = num;
    }
    return matrix;
}

int main() {
    int n = 3;
    vector<vector<int>> rowConditions = {{1,2},{2,3}};
    vector<vector<int>> colConditions = {{2,1},{3,2}};
    vector<vector<int>> result = buildMatrix(n, rowConditions, colConditions);
    for (auto& row : result) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

unordered_map<int, vector<int>> buildGraph(vector<vector<int>>& conditions, int n)Create adjacency list from conditions to represent dependencies

for (auto& cond : conditions)Add directed edges from cond[0] to cond[1]

bool dfs(int node, unordered_map<int, vector<int>>& graph, vector<int>& visited, vector<int>& stack)DFS to detect cycles and build topological order

if (visited[node] == 1) return false;Cycle detected if node is currently being visited

stack.push_back(node);Add node after visiting all descendants

vector<int> topologicalSort(vector<vector<int>>& conditions, int n)Perform topological sort or return empty if cycle detected

for (int node = 1; node <= n; node++)Visit all nodes including isolated ones

vector<int> posInRow(n + 1), posInCol(n + 1);Map numbers to row and column indices

matrix[posInRow[num]][posInCol[num]] = num;Place number in matrix at assigned position

function buildGraph(conditions, n) {
    const graph = new Map();
    for (let i = 1; i <= n; i++) graph.set(i, []);
    for (const [u, v] of conditions) {
        graph.get(u).push(v);
    }
    return graph;
}

function dfs(node, graph, visited, stack) {
    if (visited[node] === 1) return false; // cycle
    if (visited[node] === 2) return true;  // visited
    visited[node] = 1;
    for (const nei of graph.get(node)) {
        if (!dfs(nei, graph, visited, stack)) return false;
    }
    visited[node] = 2;
    stack.push(node);
    return true;
}

function topologicalSort(conditions, n) {
    const graph = buildGraph(conditions, n);
    const visited = Array(n + 1).fill(0);
    const stack = [];
    for (let node = 1; node <= n; node++) {
        if (visited[node] === 0) {
            if (!dfs(node, graph, visited, stack)) return [];
        }
    }
    stack.reverse();
    return stack;
}

function buildMatrix(n, rowConditions, colConditions) {
    const rowOrder = topologicalSort(rowConditions, n);
    if (rowOrder.length === 0) return [];
    const colOrder = topologicalSort(colConditions, n);
    if (colOrder.length === 0) return [];
    const posInRow = new Array(n + 1);
    const posInCol = new Array(n + 1);
    for (let i = 0; i < n; i++) {
        posInRow[rowOrder[i]] = i;
        posInCol[colOrder[i]] = i;
    }
    const matrix = Array.from({ length: n }, () => Array(n).fill(0));
    for (let num = 1; num <= n; num++) {
        matrix[posInRow[num]][posInCol[num]] = num;
    }
    return matrix;
}

// Driver code
const n = 3;
const rowConditions = [[1,2],[2,3]];
const colConditions = [[2,1],[3,2]];
const result = buildMatrix(n, rowConditions, colConditions);
for (const row of result) {
    console.log(row);}

Line Notes

function buildGraph(conditions, n)Create adjacency list from conditions to represent dependencies

for (const [u, v] of conditions)Add directed edges from u to v

function dfs(node, graph, visited, stack)DFS to detect cycles and build topological order

if (visited[node] === 1) return false;Cycle detected if node is currently being visited

stack.push(node);Add node after visiting all descendants

function topologicalSort(conditions, n)Perform topological sort or return empty if cycle detected

for (let node = 1; node <= n; node++)Visit all nodes including isolated ones

const posInRow = new Array(n + 1);Map numbers to row indices

matrix[posInRow[num]][posInCol[num]] = num;Place number in matrix at assigned position

⏱

Complexity

TimeO(n + m) where m is total number of conditions

SpaceO(n + m) for graph and recursion stack

We build graphs and run DFS for cycle detection and topological sort on both row and column conditions. Each edge and node is processed once.

💡 For n=1000 and m=2000, this means roughly 3000 operations, which is feasible but can be slow if implemented inefficiently.

Interview Verdict: Accepted but can be slow for very large inputs

This approach works but is not optimal for the largest constraints due to recursion overhead and repeated code.

🧠

Improved BFS-based Topological Sort (Kahn's Algorithm)

💡 Using BFS (Kahn's algorithm) for topological sort avoids recursion and stack overflow, making it more scalable and easier to understand for large inputs.

Intuition

Instead of DFS, use in-degree counts and a queue to process nodes with zero in-degree, building the order iteratively. This approach is more efficient and easier to debug.

Algorithm

1. Build adjacency lists and compute in-degree for each node for both row and column conditions.
2. Use a queue to process nodes with zero in-degree, appending them to the topological order.
3. If all nodes are processed, the order is valid; otherwise, a cycle exists.
4. Assign positions based on the topological orderings and build the matrix.

💡 This approach is easier to implement iteratively and handles large inputs without recursion issues.

</>

Code

from collections import deque, defaultdict

def topological_sort_kahn(conditions, n):
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)
    for u, v in conditions:
        graph[u].append(v)
        in_degree[v] += 1
    queue = deque([node for node in range(1, n + 1) if in_degree[node] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nei in graph[node]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) != n:
        return []
    return order

def buildMatrix(n, rowConditions, colConditions):
    row_order = topological_sort_kahn(rowConditions, n)
    if not row_order:
        return []
    col_order = topological_sort_kahn(colConditions, n)
    if not col_order:
        return []
    pos_in_row = {num: i for i, num in enumerate(row_order)}
    pos_in_col = {num: i for i, num in enumerate(col_order)}
    matrix = [[0] * n for _ in range(n)]
    for num in range(1, n + 1):
        r = pos_in_row[num]
        c = pos_in_col[num]
        matrix[r][c] = num
    return matrix

# Driver code
if __name__ == '__main__':
    n = 3
    rowConditions = [[1,2],[2,3]]
    colConditions = [[2,1],[3,2]]
    result = buildMatrix(n, rowConditions, colConditions)
    for row in result:
        print(row)

Line Notes

graph = defaultdict(list)Initialize adjacency list to represent dependencies

in_degree = [0] * (n + 1)Track number of incoming edges for each node

queue = deque([node for node in range(1, n + 1) if in_degree[node] == 0])Start with nodes having no prerequisites

while queue:Process nodes in order of zero in-degree to build topological order

in_degree[nei] -= 1Remove edge and update in-degree of neighbor

if len(order) != n:Detect cycle if not all nodes are processed

pos_in_row = {num: i for i, num in enumerate(row_order)}Map numbers to row indices for placement

matrix[r][c] = numPlace number in matrix at assigned position

import java.util.*;

public class BuildMatrixKahn {
    private static List<Integer> topologicalSortKahn(int[][] conditions, int n) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[n + 1];
        for (int i = 1; i <= n; i++) graph.put(i, new ArrayList<>());
        for (int[] cond : conditions) {
            graph.get(cond[0]).add(cond[1]);
            inDegree[cond[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int nei : graph.get(node)) {
                inDegree[nei]--;
                if (inDegree[nei] == 0) queue.offer(nei);
            }
        }
        if (order.size() != n) return new ArrayList<>();
        return order;
    }

    public static int[][] buildMatrix(int n, int[][] rowConditions, int[][] colConditions) {
        List<Integer> rowOrder = topologicalSortKahn(rowConditions, n);
        if (rowOrder.isEmpty()) return new int[0][0];
        List<Integer> colOrder = topologicalSortKahn(colConditions, n);
        if (colOrder.isEmpty()) return new int[0][0];
        int[] posInRow = new int[n + 1];
        int[] posInCol = new int[n + 1];
        for (int i = 0; i < n; i++) {
            posInRow[rowOrder.get(i)] = i;
            posInCol[colOrder.get(i)] = i;
        }
        int[][] matrix = new int[n][n];
        for (int num = 1; num <= n; num++) {
            matrix[posInRow[num]][posInCol[num]] = num;
        }
        return matrix;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] rowConditions = {{1,2},{2,3}};
        int[][] colConditions = {{2,1},{3,2}};
        int[][] result = buildMatrix(n, rowConditions, colConditions);
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

int[] inDegree = new int[n + 1];Track incoming edges count for each node

for (int[] cond : conditions)Build graph and update in-degree counts

Queue<Integer> queue = new LinkedList<>();Queue to process nodes with zero in-degree

while (!queue.isEmpty())Process nodes in BFS manner to build order

inDegree[nei]--;Remove edge and update in-degree

if (order.size() != n) return new ArrayList<>();Detect cycle if incomplete order

posInRow[rowOrder.get(i)] = i;Map number to row index for placement

matrix[posInRow[num]][posInCol[num]] = num;Place number in matrix at assigned position

#include <bits/stdc++.h>
using namespace std;

vector<int> topologicalSortKahn(vector<vector<int>>& conditions, int n) {
    unordered_map<int, vector<int>> graph;
    vector<int> inDegree(n + 1, 0);
    for (int i = 1; i <= n; i++) graph[i] = {};
    for (auto& cond : conditions) {
        graph[cond[0]].push_back(cond[1]);
        inDegree[cond[1]]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int nei : graph[node]) {
            inDegree[nei]--;
            if (inDegree[nei] == 0) q.push(nei);
        }
    }
    if ((int)order.size() != n) return {};
    return order;
}

vector<vector<int>> buildMatrix(int n, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
    vector<int> rowOrder = topologicalSortKahn(rowConditions, n);
    if (rowOrder.empty()) return {};
    vector<int> colOrder = topologicalSortKahn(colConditions, n);
    if (colOrder.empty()) return {};
    vector<int> posInRow(n + 1), posInCol(n + 1);
    for (int i = 0; i < n; i++) {
        posInRow[rowOrder[i]] = i;
        posInCol[colOrder[i]] = i;
    }
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int num = 1; num <= n; num++) {
        matrix[posInRow[num]][posInCol[num]] = num;
    }
    return matrix;
}

int main() {
    int n = 3;
    vector<vector<int>> rowConditions = {{1,2},{2,3}};
    vector<vector<int>> colConditions = {{2,1},{3,2}};
    vector<vector<int>> result = buildMatrix(n, rowConditions, colConditions);
    for (auto& row : result) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<int> inDegree(n + 1, 0);Track incoming edges count for each node

for (auto& cond : conditions)Build graph and update in-degree counts

queue<int> q;Queue to process nodes with zero in-degree

while (!q.empty())Process nodes in BFS order to build topological order

inDegree[nei]--;Remove edge and update in-degree

if ((int)order.size() != n) return {};Detect cycle if incomplete order

posInRow[rowOrder[i]] = i;Map number to row index for placement

matrix[posInRow[num]][posInCol[num]] = num;Place number in matrix at assigned position

function topologicalSortKahn(conditions, n) {
    const graph = new Map();
    const inDegree = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) graph.set(i, []);
    for (const [u, v] of conditions) {
        graph.get(u).push(v);
        inDegree[v]++;
    }
    const queue = [];
    for (let i = 1; i <= n; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    const order = [];
    while (queue.length > 0) {
        const node = queue.shift();
        order.push(node);
        for (const nei of graph.get(node)) {
            inDegree[nei]--;
            if (inDegree[nei] === 0) queue.push(nei);
        }
    }
    if (order.length !== n) return [];
    return order;
}

function buildMatrix(n, rowConditions, colConditions) {
    const rowOrder = topologicalSortKahn(rowConditions, n);
    if (rowOrder.length === 0) return [];
    const colOrder = topologicalSortKahn(colConditions, n);
    if (colOrder.length === 0) return [];
    const posInRow = new Array(n + 1);
    const posInCol = new Array(n + 1);
    for (let i = 0; i < n; i++) {
        posInRow[rowOrder[i]] = i;
        posInCol[colOrder[i]] = i;
    }
    const matrix = Array.from({ length: n }, () => Array(n).fill(0));
    for (let num = 1; num <= n; num++) {
        matrix[posInRow[num]][posInCol[num]] = num;
    }
    return matrix;
}

// Driver code
const n = 3;
const rowConditions = [[1,2],[2,3]];
const colConditions = [[2,1],[3,2]];
const result = buildMatrix(n, rowConditions, colConditions);
for (const row of result) {
    console.log(row);}

Line Notes

const inDegree = new Array(n + 1).fill(0);Track incoming edges count for each node

for (const [u, v] of conditions)Build graph and update in-degree counts

const queue = [];Queue to process nodes with zero in-degree

while (queue.length > 0)Process nodes in BFS order to build topological order

inDegree[nei]--;Remove edge and update in-degree

if (order.length !== n) return [];Detect cycle if incomplete order

posInRow[rowOrder[i]] = i;Map number to row index for placement

matrix[posInRow[num]][posInCol[num]] = num;Place number in matrix at assigned position

⏱

Complexity

TimeO(n + m) where m is total number of conditions

SpaceO(n + m) for graph and queue

Each node and edge is processed once in BFS topological sort, making it efficient for large inputs.

💡 For n=100000 and m=100000, this approach can handle the input efficiently without recursion overhead.

Interview Verdict: Accepted and efficient for large inputs

This is the preferred approach in interviews for scalability and clarity.

🧠

Optimized Construction with Position Mapping and Early Cycle Detection

💡 This approach optimizes by combining cycle detection and position assignment, and uses arrays instead of maps for faster access, suitable for very large n.

Intuition

Use Kahn's algorithm with arrays for in-degree and adjacency, detect cycles early, and assign positions immediately to avoid extra mapping steps.

Algorithm

1. Build adjacency lists and in-degree arrays for row and column conditions.
2. Perform Kahn's algorithm for both row and column orders, assigning positions as nodes are dequeued.
3. If cycle detected (not all nodes processed), return empty matrix.
4. Construct the matrix using assigned positions without extra mapping.
5. Return the constructed matrix.

💡 This approach reduces overhead by assigning positions during topological sort, improving performance.

</>

Code

from collections import deque

def topological_sort_positions(conditions, n):
    graph = [[] for _ in range(n + 1)]
    in_degree = [0] * (n + 1)
    for u, v in conditions:
        graph[u].append(v)
        in_degree[v] += 1
    queue = deque()
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            queue.append(i)
    pos = [0] * (n + 1)
    idx = 0
    while queue:
        if len(queue) > 1:
            # Multiple choices means multiple valid orders, but problem allows any
            pass
        node = queue.popleft()
        pos[node] = idx
        idx += 1
        for nei in graph[node]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if idx != n:
        return []
    return pos

def buildMatrix(n, rowConditions, colConditions):
    row_pos = topological_sort_positions(rowConditions, n)
    if not row_pos:
        return []
    col_pos = topological_sort_positions(colConditions, n)
    if not col_pos:
        return []
    matrix = [[0] * n for _ in range(n)]
    for num in range(1, n + 1):
        matrix[row_pos[num]][col_pos[num]] = num
    return matrix

# Driver code
if __name__ == '__main__':
    n = 3
    rowConditions = [[1,2],[2,3]]
    colConditions = [[2,1],[3,2]]
    result = buildMatrix(n, rowConditions, colConditions)
    for row in result:
        print(row)

Line Notes

graph = [[] for _ in range(n + 1)]Use list of lists for adjacency for fast access and memory efficiency

in_degree = [0] * (n + 1)Track incoming edges count for each node

for u, v in conditions:Build graph and update in-degree counts

queue = deque()Queue to process nodes with zero in-degree

pos = [0] * (n + 1)Array to store position of each node as assigned

pos[node] = idxAssign position immediately as node is processed

if idx != n:Detect cycle if not all nodes are processed

matrix[row_pos[num]][col_pos[num]] = numPlace number in matrix at assigned row and column

import java.util.*;

public class BuildMatrixOptimized {
    private static int[] topologicalSortPositions(int[][] conditions, int n) {
        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
        int[] inDegree = new int[n + 1];
        for (int[] cond : conditions) {
            graph[cond[0]].add(cond[1]);
            inDegree[cond[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        int[] pos = new int[n + 1];
        int idx = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            pos[node] = idx++;
            for (int nei : graph[node]) {
                inDegree[nei]--;
                if (inDegree[nei] == 0) queue.offer(nei);
            }
        }
        if (idx != n) return new int[0];
        return pos;
    }

    public static int[][] buildMatrix(int n, int[][] rowConditions, int[][] colConditions) {
        int[] rowPos = topologicalSortPositions(rowConditions, n);
        if (rowPos.length == 0) return new int[0][0];
        int[] colPos = topologicalSortPositions(colConditions, n);
        if (colPos.length == 0) return new int[0][0];
        int[][] matrix = new int[n][n];
        for (int num = 1; num <= n; num++) {
            matrix[rowPos[num]][colPos[num]] = num;
        }
        return matrix;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] rowConditions = {{1,2},{2,3}};
        int[][] colConditions = {{2,1},{3,2}};
        int[][] result = buildMatrix(n, rowConditions, colConditions);
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

List<Integer>[] graph = new ArrayList[n + 1];Use array of lists for adjacency for fast access

int[] inDegree = new int[n + 1];Track incoming edges count for each node

for (int[] cond : conditions)Build graph and update in-degree counts

Queue<Integer> queue = new LinkedList<>();Queue to process nodes with zero in-degree

pos[node] = idx++;Assign position immediately as node is processed

if (idx != n) return new int[0];Detect cycle if not all nodes processed

matrix[rowPos[num]][colPos[num]] = num;Place number in matrix at assigned position

#include <bits/stdc++.h>
using namespace std;

vector<int> topologicalSortPositions(vector<vector<int>>& conditions, int n) {
    vector<vector<int>> graph(n + 1);
    vector<int> inDegree(n + 1, 0);
    for (auto& cond : conditions) {
        graph[cond[0]].push_back(cond[1]);
        inDegree[cond[1]]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    vector<int> pos(n + 1);
    int idx = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        pos[node] = idx++;
        for (int nei : graph[node]) {
            inDegree[nei]--;
            if (inDegree[nei] == 0) q.push(nei);
        }
    }
    if (idx != n) return {};
    return pos;
}

vector<vector<int>> buildMatrix(int n, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
    vector<int> rowPos = topologicalSortPositions(rowConditions, n);
    if (rowPos.empty()) return {};
    vector<int> colPos = topologicalSortPositions(colConditions, n);
    if (colPos.empty()) return {};
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int num = 1; num <= n; num++) {
        matrix[rowPos[num]][colPos[num]] = num;
    }
    return matrix;
}

int main() {
    int n = 3;
    vector<vector<int>> rowConditions = {{1,2},{2,3}};
    vector<vector<int>> colConditions = {{2,1},{3,2}};
    vector<vector<int>> result = buildMatrix(n, rowConditions, colConditions);
    for (auto& row : result) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<int>> graph(n + 1);Use vector of vectors for adjacency for fast access

vector<int> inDegree(n + 1, 0);Track incoming edges count for each node

for (auto& cond : conditions)Build graph and update in-degree counts

queue<int> q;Queue to process nodes with zero in-degree

pos[node] = idx++;Assign position immediately as node is processed

if (idx != n) return {};Detect cycle if not all nodes processed

matrix[rowPos[num]][colPos[num]] = num;Place number in matrix at assigned position

function topologicalSortPositions(conditions, n) {
    const graph = Array.from({ length: n + 1 }, () => []);
    const inDegree = new Array(n + 1).fill(0);
    for (const [u, v] of conditions) {
        graph[u].push(v);
        inDegree[v]++;
    }
    const queue = [];
    for (let i = 1; i <= n; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    const pos = new Array(n + 1);
    let idx = 0;
    while (queue.length > 0) {
        const node = queue.shift();
        pos[node] = idx++;
        for (const nei of graph[node]) {
            inDegree[nei]--;
            if (inDegree[nei] === 0) queue.push(nei);
        }
    }
    if (idx !== n) return [];
    return pos;
}

function buildMatrix(n, rowConditions, colConditions) {
    const rowPos = topologicalSortPositions(rowConditions, n);
    if (rowPos.length === 0) return [];
    const colPos = topologicalSortPositions(colConditions, n);
    if (colPos.length === 0) return [];
    const matrix = Array.from({ length: n }, () => Array(n).fill(0));
    for (let num = 1; num <= n; num++) {
        matrix[rowPos[num]][colPos[num]] = num;
    }
    return matrix;
}

// Driver code
const n = 3;
const rowConditions = [[1,2],[2,3]];
const colConditions = [[2,1],[3,2]];
const result = buildMatrix(n, rowConditions, colConditions);
for (const row of result) {
    console.log(row);}

Line Notes

const graph = Array.from({ length: n + 1 }, () => []);Use array of arrays for adjacency for fast access

const inDegree = new Array(n + 1).fill(0);Track incoming edges count for each node

for (const [u, v] of conditions)Build graph and update in-degree counts

const queue = [];Queue to process nodes with zero in-degree

pos[node] = idx++;Assign position immediately as node is processed

if (idx !== n) return [];Detect cycle if not all nodes processed

matrix[rowPos[num]][colPos[num]] = num;Place number in matrix at assigned position

⏱

Complexity

TimeO(n + m) where m is total number of conditions

SpaceO(n + m) for adjacency and in-degree arrays

Assigning positions during topological sort avoids extra mapping, improving runtime and memory usage.

💡 This approach is best for very large inputs where performance and memory are critical.

Interview Verdict: Accepted and optimal for large scale inputs

This is the best practical approach combining clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 (BFS Kahn's algorithm) or approach 3 (optimized BFS with position assignment) are best to code due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS Cycle Detection)	O(n + m)	O(n + m)	Yes (deep recursion)	Yes	Mention only - never code due to recursion risk
2. BFS Topological Sort (Kahn's Algorithm)	O(n + m)	O(n + m)	No	Yes	Preferred approach to code
3. Optimized BFS with Position Assignment	O(n + m)	O(n + m)	No	Yes	Best for large inputs; code if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, followed by improvements. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using DFS for cycle detection and topological sort.Step 3: Explain the limitations of recursion and introduce Kahn's algorithm for BFS topological sort.Step 4: Discuss optimizations for large inputs using arrays and early position assignment.Step 5: Code the chosen approach and test with sample inputs.

Time Allocation

Clarify: 5min → Approach: 10min → Code: 15min → Test & Optimize: 10min. Total ~40min

What the Interviewer Tests

The interviewer tests your understanding of topological sort, cycle detection, handling two separate orderings, and mapping results into a matrix. They also assess your ability to optimize and handle edge cases.

Common Follow-ups

• What if conditions contain cycles? → Return empty matrix.
• Can multiple valid matrices exist? → Yes, any valid topological order is acceptable.
• How to handle isolated nodes with no conditions? → They can be placed anywhere respecting other constraints.
• What if n is very large? → Use BFS topological sort with arrays for efficiency.

💡 These follow-ups test your robustness and understanding of edge cases and scalability.

🔍

Pattern Recognition

When to Use

1) Problem involves ordering elements with dependency constraints; 2) Two separate sets of ordering constraints exist; 3) Need to combine two orderings into a 2D structure; 4) Detect cycles to validate ordering.

Signature Phrases

must come beforerowConditions and colConditionsbuild matrix satisfying orderings

NOT This Pattern When

Problems involving only sorting without dependencies or single dimension ordering

Similar Problems

Sequence Reconstruction - similar topological ordering conceptCourse Schedule II - single topological ordering with cycle detection

Practice

1. You are given a list of courses and their prerequisite pairs. You need to find an order to take all courses such that all prerequisites are satisfied. Which algorithmic approach guarantees an optimal solution to determine such an order if it exists?

easy

A. Use a greedy algorithm that always picks the course with the fewest prerequisites next.

B. Use a topological sort algorithm based on BFS and in-degree counting (Kahn's Algorithm).

C. Use dynamic programming to build up solutions from smaller subproblems.

D. Use backtracking to try all permutations of courses and check prerequisites.

Solution

1. Step 1: Understand the problem as a graph

   Courses and prerequisites form a directed graph where edges represent dependencies.

2. Step 2: Identify the algorithm that finds a linear ordering respecting dependencies

   Kahn's Algorithm uses BFS and in-degree counts to find a topological order efficiently and detects cycles.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Topological sort with BFS is the standard approach for course scheduling [OK]

Hint: Topological sort with BFS handles prerequisites and cycles [OK]

Common Mistakes:

• Thinking greedy approach always works
• Confusing DP with topological ordering
• Trying all permutations is too slow

2. Consider the following code snippet implementing the optimal solution for the longest path with different adjacent characters problem. Given n = 3, edges = [[0,1],[1,2]], and s = "aba", what is the final returned value?

easy

A. -1

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace topological order and dp array

   Topological order is [0,1,2]. Initialize dp = [1,1,1]. - For node 0: neighbor 1, s[1] = 'b' != s[0] = 'a', dp[1] = max(1, 1+1) = 2. - For node 1: neighbor 2, s[2] = 'a' != s[1] = 'b', dp[2] = max(1, 2+1) = 3.

2. Step 2: Compute final answer

   Maximum dp value is 3, which is returned.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp array ends as [1, 2, 3], max is 3 [OK]

Hint: Check dp updates along topo order carefully [OK]

Common Mistakes:

• Returning dp[node] instead of max(dp)
• Ignoring character difference condition
• Miscomputing topological order

3. Consider the following Python code implementing the optimal leaf trimming approach for Minimum Height Trees. Given n = 4 and edges = [[1,0],[1,2],[1,3]], what is the final returned list?

easy

A. [3]

B. [0, 2, 3]

C. [2]

D. [1]

Solution

1. Step 1: Initialize graph and degrees

   Nodes: 0,1,2,3; edges connect 1 to 0,2,3. Degrees: 0->1, 1->3, 2->1, 3->1. Leaves initially: [0,2,3].

2. Step 2: Trim leaves until ≤ 2 nodes remain

   Remove leaves [0,2,3], decrement neighbors' degrees. Node 1 degree reduces from 3 to 0, becomes leaf. Remaining nodes = 4 - 3 = 1. Loop ends. Return [1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only node 1 remains as centroid after trimming [OK]

Hint: Leaves trimmed until ≤2 nodes remain [OK]

Common Mistakes:

• Returning initial leaves
• Off-by-one in loop
• Not updating degrees correctly

4. The following code attempts to find eventual safe states using the reversed graph and Kahn's algorithm. Identify the line containing the subtle bug that causes incorrect results on some inputs.

from collections import deque

def eventualSafeNodes(graph):
    n = len(graph)
    reverse_graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u in range(n):
        for v in graph[u]:
            reverse_graph[v].append(u)
        in_degree[u] = len(graph[u])  # Bug fixed here

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    safe = []

    while queue:
        node = queue.popleft()
        safe.append(node)
        for prev in reverse_graph[node]:
            in_degree[prev] -= 1
            if in_degree[prev] == 0:
                queue.append(prev)

    return sorted(safe)

medium

A. Line initializing queue with nodes having in_degree zero

B. Line appending u to reverse_graph[v]

C. Line decrementing in_degree[prev] inside the while loop

D. Line setting in_degree[v] = len(graph[u]) inside the outer loop

Solution

1. Step 1: Identify in-degree assignment error

   In-degree should be assigned per node u, but the original code assigned in_degree[v] inside inner loop, overwriting multiple times incorrectly.

2. Step 2: Correct assignment

   It should be in_degree[u] = len(graph[u]) after inner loop completes, not in_degree[v].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect in-degree causes wrong queue initialization and wrong safe nodes [OK]

Hint: In-degree must be assigned per node, not per neighbor [OK]

Common Mistakes:

• Confusing in-degree and out-degree assignment
• Assigning in-degree inside inner loop incorrectly
• Misusing loop variables for in-degree

5. What is the time complexity of the optimal leaf trimming algorithm for finding Minimum Height Trees in a tree with n nodes and n-1 edges?

medium

A. O(n²) because each leaf removal requires scanning all nodes.

B. O(n) because each edge and node is processed at most once during trimming.

C. O(n log n) due to priority queue operations for leaf selection.

D. O(n + m) where m is the number of edges, which equals n-1 here.

Solution

1. Step 1: Analyze leaf trimming operations

   Each node is added and removed from the leaves queue at most once. Each edge is visited when decrementing degrees.

2. Step 2: Combine node and edge processing

   Since the graph is a tree, edges = n-1. Total operations proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity matches leaf trimming algorithm [OK]

Hint: Each node and edge processed once [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing with BFS from each node
• Thinking priority queue is used