Build a Matrix With Conditions

HARD✓ CHIP-TIMEDLC #2392 — FULL STATEMENT ↗

The drill: Place the numbers 1..k into a k×k grid, one per row and one per column, so that a list of "this value's row must come before that value's row" rules holds — and the same for columns. Report an empty grid if the rules contradict themselves.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

The numbers 1 through k need to fill a k×k grid, one value per row and one per column, so the grid is really a placement, not a free arrangement.

Two separate rulebooks constrain that placement: a list of row conditions saying one value's row must come before another's, and a list of column conditions saying the same thing about columns. Both rulebooks have to hold at once.

If either rulebook contains a contradiction that no ordering could satisfy, the task is to report that no matrix exists rather than force an invalid placement.

EX 01

k = 1 · rowConditions = [] · colConditions = []

→ [[1]]

SINGLE VALUE, NO CONDITIONS NEEDED

EX 02

k = 3 · rowConditions = [[1, 2], [2, 3]] · colConditions = [[3, 2], [2, 1]]

→ [[0, 0, 1], [0, 2, 0], [3, 0, 0]]

ROWS ASCEND, COLUMNS MIRROR IN REVERSE

EX 03

k = 4 · rowConditions = [[1, 2], [2, 3], [3, 4]] · colConditions = [[4, 3], [3, 2], [2, 1]]

→ [[0, 0, 0, 1], [0, 0, 2, 0], [0, 3, 0, 0], [4, 0, 0, 0]]

4X4 ANTI-DIAGONAL PLACEMENT

k stays small, roughly up to a few hundred
row and column condition lists are each modest in size
each value from 1 to k appears exactly once in the grid
a contradiction in either rulebook means no valid matrix exists

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Rows and columns are independent puzzles wearing the same rulebook shape: given a list of before/after pairs over the values 1..k, find an ordering that respects every pair — or prove none exists.

HINT 2 THE STRUCTURE

That's exactly topological sorting, run twice: once to decide which row each value lands in, once to decide which column. A contradiction in either one (a cycle) means no matrix can satisfy the rules.

HINT 3 ONE STEP FROM THE ANSWER

Topo-sort the row rules to get a row index per value, topo-sort the column rules to get a column index per value, then drop each value straight into matrix[rowIndex[v]][colIndex[v]] — the two sorts never need to talk to each other.

COACH'S BOARD — THE PATTERN, STEP BY STEP

TWO ORDERS, ONE GRIDPATTERN · KAHN'S BFS, TWICEk=3 · rows: 1<2<3 · cols: 3<2<1

STEP 1

Row rule: 1 before 2 before 3. Kahn's BFS peels zero-indegree values first — order comes out [1, 2, 3], top row to bottom.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/build-a-matrix-with-conditions.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        row_order = self._topo_bfs(k, rowConditions)
        if row_order is None:
            return []
        col_order = self._topo_bfs(k, colConditions)
        if col_order is None:
            return []
        row_pos = {v: i for i, v in enumerate(row_order)}
        col_pos = {v: i for i, v in enumerate(col_order)}
        matrix = [[0] * k for _ in range(k)]
        for v in range(1, k + 1):
            matrix[row_pos[v]][col_pos[v]] = v
        return matrix

    def _topo_bfs(self, k, conditions):
        graph = collections.defaultdict(list)
        indegree = [0] * (k + 1)
        for u, v in conditions:
            graph[u].append(v)
            indegree[v] += 1
        queue = collections.deque(i for i in range(1, k + 1) if indegree[i] == 0)
        order = []
        while queue:
            u = queue.popleft()
            order.append(u)
            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
        return order if len(order) == k else None

TIME O(K + E)SPACE O(K + E)PYTHON · RACE PACE · 31 LN

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        row_order = self._topo_dfs(k, rowConditions)
        if row_order is None:
            return []
        col_order = self._topo_dfs(k, colConditions)
        if col_order is None:
            return []
        row_pos = {v: i for i, v in enumerate(row_order)}
        col_pos = {v: i for i, v in enumerate(col_order)}
        matrix = [[0] * k for _ in range(k)]
        for v in range(1, k + 1):
            matrix[row_pos[v]][col_pos[v]] = v
        return matrix

    def _topo_dfs(self, k, conditions):
        graph = collections.defaultdict(list)
        for u, v in conditions:
            graph[u].append(v)
        state = [0] * (k + 1)  # 0 unvisited, 1 visiting, 2 done
        order = []
        cycle = [False]

        def dfs(u):
            state[u] = 1
            for v in graph[u]:
                if state[v] == 1:
                    cycle[0] = True
                    return
                if state[v] == 0:
                    dfs(v)
                    if cycle[0]:
                        return
            state[u] = 2
            order.append(u)

        for u in range(1, k + 1):
            if state[u] == 0:
                dfs(u)
                if cycle[0]:
                    return None
        order.reverse()
        return order

TIME O(K + E)SPACE O(K + E)PYTHON · TRAINING PACE · 43 LN

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[] rowOrder = topoBfs(k, rowConditions);
        if (rowOrder == null) return new int[0][0];
        int[] colOrder = topoBfs(k, colConditions);
        if (colOrder == null) return new int[0][0];
        int[] rowPos = new int[k + 1];
        int[] colPos = new int[k + 1];
        for (int i = 0; i < k; i++) rowPos[rowOrder[i]] = i;
        for (int i = 0; i < k; i++) colPos[colOrder[i]] = i;
        int[][] matrix = new int[k][k];
        for (int v = 1; v <= k; v++) matrix[rowPos[v]][colPos[v]] = v;
        return matrix;
    }

    private int[] topoBfs(int k, int[][] conditions) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] indegree = new int[k + 1];
        for (int[] c : conditions) {
            graph.computeIfAbsent(c[0], x -> new ArrayList<>()).add(c[1]);
            indegree[c[1]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= k; i++) {
            if (indegree[i] == 0) queue.add(i);
        }
        int[] order = new int[k];
        int idx = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order[idx++] = u;
            for (int v : graph.getOrDefault(u, Collections.emptyList())) {
                if (--indegree[v] == 0) queue.add(v);
            }
        }
        return idx == k ? order : null;
    }
}

TIME O(K + E)SPACE O(K + E)JAVA · RACE PACE · 38 LN

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        List<Integer> rowOrder = topoDfs(k, rowConditions);
        if (rowOrder == null) return new int[0][0];
        List<Integer> colOrder = topoDfs(k, colConditions);
        if (colOrder == null) return new int[0][0];
        int[] rowPos = new int[k + 1];
        int[] colPos = new int[k + 1];
        for (int i = 0; i < k; i++) rowPos[rowOrder.get(i)] = i;
        for (int i = 0; i < k; i++) colPos[colOrder.get(i)] = i;
        int[][] matrix = new int[k][k];
        for (int v = 1; v <= k; v++) matrix[rowPos[v]][colPos[v]] = v;
        return matrix;
    }

    private List<Integer> topoDfs(int k, int[][] conditions) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] c : conditions) {
            graph.computeIfAbsent(c[0], x -> new ArrayList<>()).add(c[1]);
        }
        int[] state = new int[k + 1]; // 0 unvisited, 1 visiting, 2 done
        List<Integer> order = new ArrayList<>();
        boolean[] cycle = { false };
        for (int u = 1; u <= k; u++) {
            if (state[u] == 0) {
                dfs(u, graph, state, order, cycle);
                if (cycle[0]) return null;
            }
        }
        Collections.reverse(order);
        return order;
    }

    private void dfs(int u, Map<Integer, List<Integer>> graph, int[] state, List<Integer> order, boolean[] cycle) {
        state[u] = 1;
        for (int v : graph.getOrDefault(u, Collections.emptyList())) {
            if (state[v] == 1) {
                cycle[0] = true;
                return;
            }
            if (state[v] == 0) {
                dfs(v, graph, state, order, cycle);
                if (cycle[0]) return;
            }
        }
        state[u] = 2;
        order.add(u);
    }
}

TIME O(K + E)SPACE O(K + E)JAVA · TRAINING PACE · 49 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED