Build a Matrix With Conditions

Brute Force — Testing Permutations on a 3×3 Grid — Watch how we try different row and column orderings, checking constraints for each combination until we find one that works.

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> rowPerm(k), colPerm(k);
        iota(rowPerm.begin(), rowPerm.end(), 1); // [1, 2, ..., k]
        iota(colPerm.begin(), colPerm.end(), 1);
        
        auto isValid = [&](vector<int>& perm, vector<vector<int>>& conditions) {
            vector<int> pos(k + 1);
            for (int i = 0; i < k; i++) pos[perm[i]] = i;
            for (auto& c : conditions) {
                if (pos[c[0]] >= pos[c[1]]) return false;
            }
            return true;
        };
        
        do {
            if (!isValid(rowPerm, rowConditions)) continue;
            colPerm.resize(k);
            iota(colPerm.begin(), colPerm.end(), 1);
            do {
                if (isValid(colPerm, colConditions)) {
                    vector<vector<int>> ans(k, vector<int>(k, 0));
                    vector<int> rowPos(k + 1), colPos(k + 1);
                    for (int i = 0; i < k; i++) {
                        rowPos[rowPerm[i]] = i;
                        colPos[colPerm[i]] = i;
                    }
                    for (int num = 1; num <= k; num++) {
                        ans[rowPos[num]][colPos[num]] = num;
                    }
                    return ans;
                }
            } while (next_permutation(colPerm.begin(), colPerm.end()));
        } while (next_permutation(rowPerm.begin(), rowPerm.end()));
        
        return {};
    }
};

from itertools import permutations
from typing import List

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def is_valid(perm, conditions):
            pos = {val: idx for idx, val in enumerate(perm)}
            return all(pos[a] < pos[b] for a, b in conditions)
        
        nums = list(range(1, k + 1))
        
        for row_perm in permutations(nums):
            if not is_valid(row_perm, rowConditions):
                continue
            for col_perm in permutations(nums):
                if is_valid(col_perm, colConditions):
                    row_pos = {val: idx for idx, val in enumerate(row_perm)}
                    col_pos = {val: idx for idx, val in enumerate(col_perm)}
                    matrix = [[0] * k for _ in range(k)]
                    for num in range(1, k + 1):
                        matrix[row_pos[num]][col_pos[num]] = num
                    return matrix
        
        return []

import java.util.*;

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[] nums = new int[k];
        for (int i = 0; i < k; i++) nums[i] = i + 1;
        
        List<int[]> rowPerms = new ArrayList<>();
        generatePermutations(nums, 0, rowPerms);
        
        for (int[] rowPerm : rowPerms) {
            if (!isValid(rowPerm, rowConditions, k)) continue;
            
            List<int[]> colPerms = new ArrayList<>();
            generatePermutations(nums.clone(), 0, colPerms);
            
            for (int[] colPerm : colPerms) {
                if (isValid(colPerm, colConditions, k)) {
                    int[][] matrix = new int[k][k];
                    int[] rowPos = new int[k + 1], colPos = new int[k + 1];
                    for (int i = 0; i < k; i++) {
                        rowPos[rowPerm[i]] = i;
                        colPos[colPerm[i]] = i;
                    }
                    for (int num = 1; num <= k; num++) {
                        matrix[rowPos[num]][colPos[num]] = num;
                    }
                    return matrix;
                }
            }
        }
        return new int[][]{};
    }
    
    private boolean isValid(int[] perm, int[][] conditions, int k) {
        int[] pos = new int[k + 1];
        for (int i = 0; i < perm.length; i++) pos[perm[i]] = i;
        for (int[] c : conditions) {
            if (pos[c[0]] >= pos[c[1]]) return false;
        }
        return true;
    }
    
    private void generatePermutations(int[] arr, int start, List<int[]> result) {
        if (start == arr.length) {
            result.add(arr.clone());
            return;
        }
        for (int i = start; i < arr.length; i++) {
            int temp = arr[start]; arr[start] = arr[i]; arr[i] = temp;
            generatePermutations(arr, start + 1, result);
            temp = arr[start]; arr[start] = arr[i]; arr[i] = temp;
        }
    }
}

Topological Sort (BFS) — Row Constraint Graph — Watch Kahn's algorithm process the row constraint graph, removing nodes with zero in-degree to build a valid top-to-bottom ordering.

Topological Sort (BFS) — Column Constraint Graph — Watch Kahn's algorithm process the column constraints, building a valid left-to-right ordering.

Matrix Construction — Combining Row and Column Orderings — Watch how we place each number at the intersection of its row position (from row topological sort) and column position (from column topological sort).

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions,
                                    vector<vector<int>>& colConditions) {
        vector<int> rowOrder = topologicalSort(rowConditions, k);
        if (rowOrder.empty()) return {};
        
        vector<int> colOrder = topologicalSort(colConditions, k);
        if (colOrder.empty()) return {};
        
        // Build column position mapping
        vector<int> colPos(k + 1);
        for (int j = 0; j < k; j++) {
            colPos[colOrder[j]] = j;
        }
        
        // Construct the matrix
        vector<vector<int>> ans(k, vector<int>(k, 0));
        for (int i = 0; i < k; i++) {
            int num = rowOrder[i];
            ans[i][colPos[num]] = num;
        }
        return ans;
    }
    
private:
    vector<int> topologicalSort(vector<vector<int>>& conditions, int k) {
        vector<vector<int>> graph(k + 1);
        vector<int> inDegree(k + 1, 0);
        
        for (auto& cond : conditions) {
            graph[cond[0]].push_back(cond[1]);
            inDegree[cond[1]]++;
        }
        
        queue<int> q;
        for (int i = 1; i <= k; 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 neighbor : graph[node]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        return order.size() == k ? order : vector<int>();
    }
};

from collections import defaultdict, deque
from typing import List

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]],
                    colConditions: List[List[int]]) -> List[List[int]]:
        
        def topological_sort(conditions: List[List[int]]) -> List[int]:
            graph = defaultdict(list)
            in_degree = [0] * (k + 1)
            
            for a, b in conditions:
                graph[a].append(b)
                in_degree[b] += 1
            
            queue = deque(i for i in range(1, k + 1) if in_degree[i] == 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 []
        
        row_order = topological_sort(rowConditions)
        if not row_order:
            return []
        
        col_order = topological_sort(colConditions)
        if not col_order:
            return []
        
        # Map each number to its column position
        col_pos = {num: j for j, num in enumerate(col_order)}
        
        # Build the matrix
        matrix = [[0] * k for _ in range(k)]
        for i, num in enumerate(row_order):
            matrix[i][col_pos[num]] = num
        
        return matrix

import java.util.*;

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[] rowOrder = topologicalSort(rowConditions, k);
        if (rowOrder.length == 0) return new int[][]{};
        
        int[] colOrder = topologicalSort(colConditions, k);
        if (colOrder.length == 0) return new int[][]{};
        
        // Build column position mapping
        int[] colPos = new int[k + 1];
        for (int j = 0; j < k; j++) {
            colPos[colOrder[j]] = j;
        }
        
        // Construct the matrix
        int[][] matrix = new int[k][k];
        for (int i = 0; i < k; i++) {
            int num = rowOrder[i];
            matrix[i][colPos[num]] = num;
        }
        return matrix;
    }
    
    private int[] topologicalSort(int[][] conditions, int k) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[k + 1];
        
        for (int i = 0; i <= k; i++) graph.add(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 <= k; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        
        int[] order = new int[k];
        int idx = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order[idx++] = node;
            for (int neighbor : graph.get(node)) {
                if (--inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return idx == k ? order : new int[]{};
    }
}