Graph Question - Hard Level - Question 2

2392. Build a Matrix With Conditions

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

a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and

a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti].

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 abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.

The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.

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

Constraints:

2 <= k <= 400

1 <= rowConditions.length, colConditions.length <= 10^4

rowConditions[i].length == colConditions[i].length == 2

1 <= abovei, belowi, lefti, righti <= k

abovei != belowi

lefti != righti

Analysis

This question is about ranking, so the first option should be topological sorting.

With topo sort, we can not only check the rankings, but also detect the dependency cycles.

In this question, if we can detect any dependency cycles, we can return empty matrix right away.

Otherwise, we can assign the indexes based on ranking.

To avoid possible collision, we can assign the indexes in a greedy way:

Based on the fact that we only have n elements to be assigned, and for each dimension we also have n possible values, we can assign the one index to one element. One way is to increase the next index by +1 after assigning one element.

See the codes below:

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<vector<int>> res;
        vector<vector<int>> lays1, lays2;
        // if has cycles, return empty matrix
        if(topoCounts(k, rowConditions, lays1) < k) return res;
        if(topoCounts(k, colConditions, lays2) < k) return res;
        vector<vector<int>> ids(k+1, vector<int>(2, 0));
        // assign ids greedily, to avoid collisions
        assignIds(ids, lays1, 0);
        assignIds(ids, lays2, 1);
        res.resize(k, vector<int>(k, 0));
        for(int i=1; i<=k; ++i) {
            res[ids[i][0]][ids[i][1]] = i;
        }
        return res;
    }
private:
    int topoCounts(int k, vector<vector<int>>& rs, vector<vector<int>>& lays) {
        vector<vector<int>> g(k+1);
        vector<int> inds(k+1, 0);
        for(auto &a : rs) {
            g[a[0]].push_back(a[1]);
            ++inds[a[1]];
        }
        queue<int> q;
        for(int i=1; i<=k; ++i) {
            if(inds[i]==0) q.push(i);
        }
        int res = 0;
        while(q.size()) {
            int x = q.size();
            res += x;
            vector<int> ts;
            for(int i=0; i<x; ++i) {
                auto t = q.front();
                q.pop();
                ts.push_back(t);
                for(auto &a : g[t]) {
                    --inds[a];
                    if(inds[a] == 0) q.push(a);
                }
            }
            lays.push_back(ts);
        }
        return res;
    }
    void assignIds(vector<vector<int>>& ids, vector<vector<int>>& ranks, int di) {
        int id = 0;
        for(auto &a : ranks) {
            for(auto &b : a) {
                ids[b][di] = id++;
            }
        }
    }
};

Upper Level