Build a Matrix With Conditions

Leetcode Problem:

• Build a Matrix With Conditions

Summary

• Given a 2D array of row conditions and column conditions, build a k x k matrix that contains each number from 1 to k exactly once and satisfies the conditions.

Approach

• The solution uses a depth-first search (DFS) approach to find a Hamiltonian path in the graph
• It first constructs two graphs, one for row conditions and one for column conditions
• Then, it checks if there is a cycle in either graph using DFS
• If there is a cycle, it returns an empty matrix
• Otherwise, it uses another DFS to find a Hamiltonian path in the graph and constructs the matrix based on the path.

Complexity

• O(k * m * n * k) where m and n are the number of row conditions and column conditions respectively

Explain

• The solution starts by constructing two graphs, one for row conditions and one for column conditions
• It then checks if there is a cycle in either graph using DFS
• If there is a cycle, it returns an empty matrix
• Otherwise, it uses another DFS to find a Hamiltonian path in the graph and constructs the matrix based on the path
• The Hamiltonian path is used to ensure that each number from 1 to k is used exactly once in the matrix and that the row and column conditions are satisfied.

Solution Code:

class Solution {
public:
    bool traversalCycle(int cur, vector> graph, int color[]){
        color[cur] = 1;
        for(int i = 0 ; i < graph[cur].size(); i++){
            int next = graph[cur][i];
            if (color[next] == 0 && traversalCycle(next, graph, color)){
                return true;
            } else if (color[next] == 1){
                return true;
            }
        }
        color[cur] = 2;
        return false;
    }
    bool findCycle(int k, vector> &graph){
        int *color = new int[k];
        for(int i = 0 ; i < k; i++){
            color[i] = 0;
        }
        for(int i = 0 ; i < k ;i++){
            if (color[i] != 0) continue;
            if (traversalCycle(i, graph, color)){
                return true;
            }
        }
        return false;
    }

    void traversalAnswer(int cur, vector> &graph, vector &ans, bool visited[]){
        if(visited[cur]) return;
        visited[cur] = true;
        for(int i = 0 ; i < graph[cur].size(); i++){
            int next = graph[cur][i];
            traversalAnswer(next, graph, ans, visited);
        }
        ans.push_back(cur);
    }
    void getAnswer(int k, vector> &graph, vector &ans){
        bool *visited = new bool[k];
        for(int i = 0 ; i < k; i++){
            visited[i] = false;
        }
        for(int i = 0; i < k; i++){
            if (visited[i]) continue;
            traversalAnswer(i, graph, ans, visited);
        }
        reverse(ans.begin(), ans.end());
    }

    vector> buildMatrix(int k, vector>& rowConditions, vector>& colConditions) {
        vector> graph1(k);
        vector> graph2(k);
        for(int i = 0 ; i < rowConditions.size(); i++){
            int a = rowConditions[i][0];
            int b = rowConditions[i][1];
            graph1[a - 1].push_back(b - 1);
        }
        for(int i = 0 ; i < colConditions.size(); i++){
            int a = colConditions[i][0];
            int b = colConditions[i][1];
            graph2[a - 1].push_back(b - 1);
        }
        if (findCycle(k, graph1) || findCycle(k, graph2)){
            return {};
        }

        vector ans1, ans2;
        getAnswer(k, graph1, ans1);
        getAnswer(k ,graph2, ans2);

        vector> ans;
        map m;
        for(int i = 0 ; i < k; i++){
            m[ans2[i]] = i;
            ans.push_back(vector());
            for(int j = 0 ; j < k; j++){
                ans[i].push_back(0);
            }
        }
        for(int i = 0 ; i < k; i++){
            ans[i][m[ans1[i]]] = ans1[i] + 1;
        }
        return ans;
    }
};