Build a Matrix with Conditions

Problem#

Place numbers [1..k] in a k × k grid (rest zeroes) so that for every “row condition” [a, b], a is in a row before b; same for column conditions. Return any valid grid, or [].

Examples#

k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] → a valid placement.

Approach#

Topological sort [1..k] twice (independently): once on row constraints, once on column constraints. The resulting orders give each number’s row and column. Construct the grid by placing each v at (rowRank[v], colRank[v]).

Solution#

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        auto topo = [&](vector<vector<int>>& cond) {
            vector<vector<int>> adj(k + 1);
            vector<int> indeg(k + 1, 0);
            for (auto& c : cond) {
                adj[c[0]].push_back(c[1]);
                ++indeg[c[1]];
            }
            queue<int> q;
            for (int i = 1; i <= k; ++i) if (indeg[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]) if (--indeg[v] == 0) q.push(v);
            }
            return (int)order.size() == k ? order : vector<int>{};
        };
        auto rows = topo(rowConditions);
        auto cols = topo(colConditions);
        if (rows.empty() || cols.empty()) return {};
        vector<int> rPos(k + 1), cPos(k + 1);
        for (int i = 0; i < k; ++i) { rPos[rows[i]] = i; cPos[cols[i]] = i; }
        vector<vector<int>> mat(k, vector<int>(k, 0));
        for (int v = 1; v <= k; ++v) mat[rPos[v]][cPos[v]] = v;
        return mat;
    }
};

func buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {
    topo := func(cond [][]int) []int {
        adj := make([][]int, k+1)
        indeg := make([]int, k+1)
        for _, c := range cond {
            adj[c[0]] = append(adj[c[0]], c[1])
            indeg[c[1]]++
        }
        q := []int{}
        for i := 1; i <= k; i++ {
            if indeg[i] == 0 {
                q = append(q, i)
            }
        }
        order := []int{}
        for len(q) > 0 {
            u := q[0]
            q = q[1:]
            order = append(order, u)
            for _, v := range adj[u] {
                indeg[v]--
                if indeg[v] == 0 {
                    q = append(q, v)
                }
            }
        }
        if len(order) == k {
            return order
        }
        return nil
    }
    rows := topo(rowConditions)
    cols := topo(colConditions)
    if rows == nil || cols == nil {
        return [][]int{}
    }
    rPos := make([]int, k+1)
    cPos := make([]int, k+1)
    for i := 0; i < k; i++ {
        rPos[rows[i]] = i
        cPos[cols[i]] = i
    }
    mat := make([][]int, k)
    for i := range mat {
        mat[i] = make([]int, k)
    }
    for v := 1; v <= k; v++ {
        mat[rPos[v]][cPos[v]] = v
    }
    return mat
}

from collections import deque
from typing import List

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo(cond: List[List[int]]) -> List[int]:
            adj = [[] for _ in range(k + 1)]
            indeg = [0] * (k + 1)
            for a, b in cond:
                adj[a].append(b)
                indeg[b] += 1
            q = deque(i for i in range(1, k + 1) if indeg[i] == 0)
            order: List[int] = []
            while q:
                u = q.popleft()
                order.append(u)
                for v in adj[u]:
                    indeg[v] -= 1
                    if indeg[v] == 0:
                        q.append(v)
            return order if len(order) == k else []

        rows = topo(rowConditions)
        cols = topo(colConditions)
        if not rows or not cols:
            return []
        r_pos = [0] * (k + 1)
        c_pos = [0] * (k + 1)
        for i in range(k):
            r_pos[rows[i]] = i
            c_pos[cols[i]] = i
        mat = [[0] * k for _ in range(k)]
        for v in range(1, k + 1):
            mat[r_pos[v]][c_pos[v]] = v
        return mat

var buildMatrix = function(k, rowConditions, colConditions) {
    const topo = (cond) => {
        const adj = Array.from({ length: k + 1 }, () => []);
        const indeg = new Array(k + 1).fill(0);
        for (const [a, b] of cond) {
            adj[a].push(b);
            indeg[b]++;
        }
        const q = [];
        for (let i = 1; i <= k; i++) if (indeg[i] === 0) q.push(i);
        const order = [];
        while (q.length > 0) {
            const u = q.shift();
            order.push(u);
            for (const v of adj[u]) {
                if (--indeg[v] === 0) q.push(v);
            }
        }
        return order.length === k ? order : [];
    };
    const rows = topo(rowConditions);
    const cols = topo(colConditions);
    if (rows.length === 0 || cols.length === 0) return [];
    const rPos = new Array(k + 1).fill(0);
    const cPos = new Array(k + 1).fill(0);
    for (let i = 0; i < k; i++) {
        rPos[rows[i]] = i;
        cPos[cols[i]] = i;
    }
    const mat = Array.from({ length: k }, () => new Array(k).fill(0));
    for (let v = 1; v <= k; v++) mat[rPos[v]][cPos[v]] = v;
    return mat;
};

class Solution {
    private int k;

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        this.k = k;
        int[] rows = topo(rowConditions);
        int[] cols = topo(colConditions);
        if (rows.length == 0 || cols.length == 0) return new int[0][0];
        int[] rPos = new int[k + 1];
        int[] cPos = new int[k + 1];
        for (int i = 0; i < k; i++) {
            rPos[rows[i]] = i;
            cPos[cols[i]] = i;
        }
        int[][] mat = new int[k][k];
        for (int v = 1; v <= k; v++) mat[rPos[v]][cPos[v]] = v;
        return mat;
    }

    private int[] topo(int[][] cond) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= k; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[k + 1];
        for (int[] c : cond) {
            adj.get(c[0]).add(c[1]);
            indeg[c[1]]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= k; i++) if (indeg[i] == 0) q.offer(i);
        int[] order = new int[k];
        int idx = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            order[idx++] = u;
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return idx == k ? order : new int[0];
    }
}

function buildMatrix(k: number, rowConditions: number[][], colConditions: number[][]): number[][] {
    const topo = (cond: number[][]): number[] => {
        const adj: number[][] = Array.from({ length: k + 1 }, () => []);
        const indeg: number[] = new Array(k + 1).fill(0);
        for (const [a, b] of cond) {
            adj[a].push(b);
            indeg[b]++;
        }
        const q: number[] = [];
        for (let i = 1; i <= k; i++) if (indeg[i] === 0) q.push(i);
        const order: number[] = [];
        while (q.length > 0) {
            const u = q.shift()!;
            order.push(u);
            for (const v of adj[u]) {
                if (--indeg[v] === 0) q.push(v);
            }
        }
        return order.length === k ? order : [];
    };
    const rows = topo(rowConditions);
    const cols = topo(colConditions);
    if (rows.length === 0 || cols.length === 0) return [];
    const rPos: number[] = new Array(k + 1).fill(0);
    const cPos: number[] = new Array(k + 1).fill(0);
    for (let i = 0; i < k; i++) {
        rPos[rows[i]] = i;
        cPos[cols[i]] = i;
    }
    const mat: number[][] = Array.from({ length: k }, () => new Array(k).fill(0));
    for (let v = 1; v <= k; v++) mat[rPos[v]][cPos[v]] = v;
    return mat;
}

Editorial#

Row and column constraints are independent — neither involves the other dimension. Two topological sorts give consistent orders per axis; combined they place each value at a unique row × column.

Complexity#

Time: O(k²).
Space: O(k²).

Problem#

Examples#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#