Build a Matrix With Conditions

NeetCode: Build a Matrix With Conditions · LeetCode: 2392. Build a Matrix With Conditions · Difficulty: Hard

You are given a positive integer k, rowConditions[i] = [above, below] (number above must be in a strictly higher row than below) and colConditions[i] = [left, right] (number left must be in a strictly earlier column than right). Build a k x k matrix that contains every number 1..k exactly once (all other cells 0) and satisfies every condition, or return an empty matrix (new int[0][]) if that is impossible.

Example

Text

Input:  k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
Output: a valid matrix, for instance [[0,0,1],[3,0,0],[0,2,0]]
Input:  k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
Output: []   (the row conditions contain the cycle 1 -> 2 -> 3 -> 1)

The answer is not unique, so the programs below check validity with a small verifier instead of comparing against one specific matrix.

Brute force: try every ordering

Rows and columns are independent: the row conditions constrain only the order of the numbers by row, and the column conditions only by column. If every number gets its own row and its own column (a permutation matrix), the two problems separate.

So find one permutation of 1..k that satisfies all row conditions and another that satisfies all column conditions. The brute force generates permutations recursively and tests each against the conditions. There are k! permutations, each checked in O(k + m).

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    // Does `order` (a permutation of 1..k) satisfy every (a, b): a before b ?
    private boolean satisfies(int k, List<Integer> order, int[][] conds) {
        int[] pos = new int[k + 1];
        for (int i = 0; i < order.size(); i++) pos[order.get(i)] = i;
        for (int[] c : conds) {
            if (pos[c[0]] >= pos[c[1]]) return false;
        }
        return true;
    }

    // Returns the first permutation that satisfies the conditions, or null.
    private List<Integer> findOrder(int k, List<Integer> cur, boolean[] used, int[][] conds) {
        if (cur.size() == k) {
            return satisfies(k, cur, conds) ? new ArrayList<>(cur) : null;
        }
        for (int v = 1; v <= k; v++) {
            if (!used[v]) {
                used[v] = true;
                cur.add(v);
                List<Integer> found = findOrder(k, cur, used, conds);
                if (found != null) return found;
                cur.remove(cur.size() - 1);
                used[v] = false;
            }
        }
        return null;
    }

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        List<Integer> ro = findOrder(k, new ArrayList<>(), new boolean[k + 1], rowConditions);
        List<Integer> co = findOrder(k, new ArrayList<>(), new boolean[k + 1], colConditions);
        if (ro == null || co == null) return new int[0][];
        int[] colOf = new int[k + 1];
        for (int c = 0; c < k; c++) colOf[co.get(c)] = c;
        int[][] matrix = new int[k][k];
        for (int r = 0; r < k; r++) {
            int v = ro.get(r);
            matrix[r][colOf[v]] = v;
        }
        return matrix;
    }
}

public class Main {
    // Checks that the matrix holds 1..k once each and satisfies every condition.
    static boolean isValid(int k, int[][] rows, int[][] cols, int[][] m) {
        int[] atRow = new int[k + 1];
        int[] atCol = new int[k + 1];
        boolean[] seen = new boolean[k + 1];
        for (int r = 0; r < m.length; r++) {
            for (int c = 0; c < m[r].length; c++) {
                int v = m[r][c];
                if (v != 0) {
                    if (v < 1 || v > k || seen[v]) return false;
                    seen[v] = true;
                    atRow[v] = r;
                    atCol[v] = c;
                }
            }
        }
        for (int v = 1; v <= k; v++) if (!seen[v]) return false;
        for (int[] c : rows) if (atRow[c[0]] >= atRow[c[1]]) return false;
        for (int[] c : cols) if (atCol[c[0]] >= atCol[c[1]]) return false;
        return true;
    }

    static void run(int k, int[][] rows, int[][] cols) {
        int[][] m = new Solution().buildMatrix(k, rows, cols);
        if (m.length == 0) {
            System.out.println("empty");
        } else {
            System.out.println(Arrays.deepToString(m) + " valid=" + isValid(k, rows, cols, m));
        }
    }

    public static void main(String[] args) {
        run(3, new int[][]{{1, 2}, {3, 2}}, new int[][]{{2, 1}, {3, 2}});
        run(3, new int[][]{{1, 2}, {2, 3}, {3, 1}, {2, 3}}, new int[][]{{2, 1}});
        run(1, new int[][]{}, new int[][]{});
    }
}

Output

[[0, 0, 1], [3, 0, 0], [0, 2, 0]] valid=true
empty
[[1]] valid=true

cur.remove(cur.size() - 1) removes by position, because the argument is an int. Removing a value from a List<Integer> would need an Integer argument instead.

Time: O(k! · (k + m)) where m is the number of conditions. Space: O(k + m).

Optimal: two topological sorts

"a must come before b" is a directed edge a -> b. A permutation satisfying all such edges is a topological order of the graph, and one exists if and only if the graph has no cycle. Kahn's algorithm produces one in linear time by repeatedly removing a vertex with in-degree 0. If it removes fewer than k vertices, there is a cycle and the answer is empty.

Steps:

Write one helper topo(k, conds): build adjacency lists and in-degrees, put every vertex with in-degree 0 in a queue, then repeatedly pop u, append it to the order, and decrement its neighbours (queueing those that reach 0).
If the order has fewer than k vertices there is a cycle, so return null.
Call topo on the row conditions and again on the column conditions. The position of v in the first order is its row, and in the second its column.
Put every value v at (rowOf[v], colOf[v]). Each number gets a distinct row and a distinct column, so cells never collide.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

class Solution {
    // Kahn's algorithm on vertices 1..k; null if the conditions contain a cycle.
    private int[] topo(int k, int[][] conds) {
        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 : conds) {
            adj.get(c[0]).add(c[1]);
            indeg[c[1]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int v = 1; v <= k; v++) {
            if (indeg[v] == 0) queue.add(v);
        }
        int[] order = new int[k];
        int count = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order[count++] = u;
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) queue.add(v);
            }
        }
        return count == k ? order : null;
    }

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[] ro = topo(k, rowConditions);
        int[] co = topo(k, colConditions);
        if (ro == null || co == null) return new int[0][];
        int[] colOf = new int[k + 1];
        for (int c = 0; c < k; c++) colOf[co[c]] = c;
        int[][] matrix = new int[k][k];
        for (int r = 0; r < k; r++) {
            matrix[r][colOf[ro[r]]] = ro[r];
        }
        return matrix;
    }
}

public class Main {
    // Checks that the matrix holds 1..k once each and satisfies every condition.
    static boolean isValid(int k, int[][] rows, int[][] cols, int[][] m) {
        int[] atRow = new int[k + 1];
        int[] atCol = new int[k + 1];
        boolean[] seen = new boolean[k + 1];
        for (int r = 0; r < m.length; r++) {
            for (int c = 0; c < m[r].length; c++) {
                int v = m[r][c];
                if (v != 0) {
                    if (v < 1 || v > k || seen[v]) return false;
                    seen[v] = true;
                    atRow[v] = r;
                    atCol[v] = c;
                }
            }
        }
        for (int v = 1; v <= k; v++) if (!seen[v]) return false;
        for (int[] c : rows) if (atRow[c[0]] >= atRow[c[1]]) return false;
        for (int[] c : cols) if (atCol[c[0]] >= atCol[c[1]]) return false;
        return true;
    }

    static void run(int k, int[][] rows, int[][] cols) {
        int[][] m = new Solution().buildMatrix(k, rows, cols);
        if (m.length == 0) {
            System.out.println("empty");
        } else {
            System.out.println(Arrays.deepToString(m) + " valid=" + isValid(k, rows, cols, m));
        }
    }

    public static void main(String[] args) {
        run(3, new int[][]{{1, 2}, {3, 2}}, new int[][]{{2, 1}, {3, 2}});
        run(3, new int[][]{{1, 2}, {2, 3}, {3, 1}, {2, 3}}, new int[][]{{2, 1}});
        run(1, new int[][]{}, new int[][]{});
    }
}

Output

[[0, 0, 1], [3, 0, 0], [0, 2, 0]] valid=true
empty
[[1]] valid=true

Time: O(k^2 + m): each sort is O(k + m), and allocating the k x k matrix costs O(k^2). Space: O(k^2 + m) for the matrix and graphs.

Both programs print valid=true for the first case, although the matrices they build can differ because several orderings are correct. Duplicate conditions (like the repeated [2,3]) are harmless: the in-degree is incremented once per copy and decremented once per copy. ArrayDeque rejects null, which is not a problem here because the queue holds vertex numbers.

How to explain it in an interview

Brute force: try permutations of 1..k for the rows and for the columns until one satisfies the conditions, O(k!).
Key idea: rows and columns are independent, and "a above b" is a directed edge, so each dimension is a topological sort. A cycle means the answer is empty.
Steps: (1) topo with Kahn's queue, returning null if fewer than k vertices come out; (2) run it on the rows and on the columns; (3) invert the column order into colOf; (4) fill matrix[row][colOf[v]] = v.
Complexity: time O(k^2 + m) (the matrix itself has k^2 cells), space O(k^2 + m).
Pitfalls: duplicate conditions are fine because in-degrees count every copy. The answer is not unique, so any valid topological order works. Return an empty matrix if either sort finds a cycle.