2392. Build a Matrix with Conditions

Problem Statement

2392. Build a Matrix With Conditions

Hard

You are given a positive integer k. You are also given:

a 2D integer array rowConditions of size n where rowConditions[i] = [above_i, below_i], and
a 2D integer array colConditions of size m where colConditions[i] = [left_i, right_i].

The two arrays contain integers from 1 to k.

You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0.

The matrix should also satisfy the following conditions:

The number above_i should appear in a row that is strictly above the row at which the number below_i appears for all i from 0 to n - 1.
The number left_i should appear in a column that is strictly left of the column at which the number right_i appears for all i from 0 to m - 1.

Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

Example 1:

Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
Output: [[3,0,0],[0,0,1],[0,2,0]]
Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions.
The row conditions are the following:
- Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix.
- Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix.
The column conditions are the following:
- Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix.
- Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix.
Note that there may be multiple correct answers.

Example 2:

Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
Output: []
Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied.
No matrix can satisfy all the conditions, so we return the empty matrix.

Constraints:

2 <= k <= 400
1 <= rowConditions.length, colConditions.length <= 10⁴
rowConditions[i].length == colConditions[i].length == 2
1 <= above_i, below_i, left_i, right_i <= k
above_i != below_i
left_i != right_i

Java — topological sort

Source file

class Solution {
    private void dfs(List<List<Integer>> adj, int[] vis, int V, List<Integer> order, boolean[] hasCycle) {
        vis[V] = 1;
        for (int nbr : adj.get(V)) {
            if (vis[nbr] == 0) {
                dfs(adj, vis, nbr, order, hasCycle);
                if (hasCycle[0])
                    return;
            } else if (vis[nbr] == 1) { // same node appeared twice in same dfs route
                hasCycle[0] = true;
                return;
            }
        }
        vis[V] = 2; // Route complete w/o cycles
        order.add(V);
    }

    private List<Integer> topoSort(int[][] edges, int n) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            adj.add(new ArrayList<>());
        for (int[] e : edges)
            adj.get(e[0]).add(e[1]);
        int[] vis = new int[n + 1]; // 0: not visited, 1: visiting in current dfs, 2: visited
        boolean[] hasCycle = { false }; // 1 boolean value pass by reference 
        List<Integer> order = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 0) {
                dfs(adj, vis, i, order, hasCycle);
                if (hasCycle[0])
                    return new ArrayList<>(); // Not a DAG
            }
        }
        Collections.reverse(order);
        return order;
    }

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[][] matrix = new int[k][k];
        List<Integer> rowOrder = topoSort(rowConditions, k);
        List<Integer> colOrder = topoSort(colConditions, k);
        if (rowOrder.isEmpty() || colOrder.isEmpty()) // Either !DAG
            return new int[0][0]; // matrix generation infeasible
        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++)
                if (rowOrder.get(i).equals(colOrder.get(j)))
                    matrix[i][j] = rowOrder.get(i);
        return matrix;
    }
}

Java

Source file

class Solution {
    private int[] topoSort(int[][] edges, int n) {  // Kahn's algo
        List<Integer>[] adj = new ArrayList[n+1];
        int[] indegree = new int[n+1], order = new int[n];
        for (int i = 0; i <= n; i++)
            adj[i] = new ArrayList<>();
        for (int[] e : edges){
            adj[e[0]].add(e[1]);
            indegree[e[1]]++;    
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i=1; i<=n; i++)
            if(indegree[i]==0)
                q.offer(i);
        int idx = 0;
        while(!q.isEmpty()){
            int V = q.poll();
            order[idx++] = V;
            n--;
            for(int nbr: adj[V]){
                if(--indegree[nbr]==0)
                    q.offer(nbr);
            }
        }
        if(n>0) // ain't a DAG
            return new int[0];
        return order;
    }

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[][] matrix = new int[k][k];
        int[] rowOrder = topoSort(rowConditions, k);
        int[] colOrder = topoSort(colConditions, k);
        if (rowOrder.length == 0 || colOrder.length == 0) // Either is !DAG
            return new int[0][0]; // matrix generation infeasible
        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++)
                if (rowOrder[i]==colOrder[j])
                    matrix[i][j] = rowOrder[i];
        return matrix;
    }
}