Build a Matrix With Conditions LeetCode Solution

Problem – Build a Matrix With Conditions LeetCode Solution

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.

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 <= 104
  • rowConditions[i].length == colConditions[i].length == 2
  • 1 <= abovei, belowi, lefti, righti <= k
  • abovei != belowi
  • lefti != righti

Build a Matrix With Conditions LeetCode Solution in C++

class Solution {
    
    /* 1. Checking if cycle is present - If YES, Topological Sort is not possible */
    vector<char> color;
    bool dfs(int v, vector<vector<int>>& graph) {
        color[v] = 1;
        for (int u : graph[v]) {
            if (color[u] == 0) {
                if (dfs(u, graph))
                    return true;
            } else if (color[u] == 1) {
                return true;
            }
        }
        color[v] = 2;
        return false;
    }
    bool find_cycle(vector<vector<int>>& graph, int n) {
        color.assign(n, 0);

        for (int v = 0; v < n; v++) {
            if (color[v] == 0 && dfs(v, graph))
                return true;
        }
        return false;
    }

    /* 2. Forming the Topological Sort for DAG */
    vector<bool> visited;
    void dfs2(int v, vector<vector<int>>& graph, vector<int>& ans) {
        visited[v] = true;
        for (int u : graph[v]) {
            if (!visited[u])
                dfs2(u, graph, ans);
        }
        ans.push_back(v);
    }

    void topological_sort(vector<vector<int>>& graph, int n, vector<int>& ans) {
        visited.assign(n, false);
        ans.clear();
        for (int i = 0; i < n; ++i) {
            if (!visited[i])
                dfs2(i, graph, ans);
        }
        reverse(ans.begin(), ans.end());
    }
    
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<vector<int>> graph1(k);
        vector<vector<int>> graph2(k);
        
        for(auto x:rowConditions) {
            graph1[x[0] - 1].push_back(x[1] - 1);
        }
        for(auto x:colConditions) {
            graph2[x[0] - 1].push_back(x[1] - 1);
        }
        
        /* 3. Check if CYCLE present in any of the graphs */
        if(find_cycle(graph1, k) || find_cycle(graph2, k)) return vector<vector<int>>();
        
        /* 4. Forming Topological Sort for the DAGs */
        vector<int> ans1; vector<int> ans2;
        
        topological_sort(graph1, k, ans1);
        topological_sort(graph2, k, ans2);
        
        /* 5. Forming the answer from the rowPosition and colPosition for each element */
        vector<vector<int>> ans(k, vector<int>(k));
        
        map<int, int> m;
        for(int i = 0; i < k; i++) {
            m[ans2[i]] = i;
        }
        
        for(int i = 0; i < k; i++) {
            ans[i][m[ans1[i]]] = ans1[i] + 1;
        }
        
        return ans;
    }
};

Build a Matrix With Conditions LeetCode Solution in Java

class Solution {
    
    List<Integer>[] al;
    
    public int[][] buildMatrix(int k, int[][] rc, int[][] cc) {
        
        int ans[][] = new int[k][k];
        this.al = new ArrayList[k+1];
        
        for(int i=0;i<=k;i++) al[i] = new ArrayList<>();
        for(int r[] : rc) al[r[0]].add(r[1]);
        
        boolean[] vis = new boolean[k+1];
        boolean dfsvis[] = new boolean[k+1];
        List<Integer> rowStack = new ArrayList<>();
        
        for(int node=1;node<=k;node++){
            if(!vis[node]) {
                if(!dfs(node,vis,rowStack,dfsvis)) return new int[0][0];
            }
        }

        for(int i=0;i<=k;i++) al[i] = new ArrayList<>();
        for(int c[] : cc) al[c[0]].add(c[1]);
        List<Integer> colStack = new ArrayList<>();
        
        vis = new boolean[k+1];
        dfsvis = new boolean[k+1];
        
        for(int node=1;node<=k;node++){
            if(!vis[node]) {
                if(!dfs(node,vis,colStack,dfsvis)) return new int[0][0];
            }
        }
        
        HashMap<Integer,Integer> map = new HashMap<>();
        
        for(int i=0;i<colStack.size();i++){
            map.put(colStack.get(i),i);
        }
        
        int row = 0;
        
        for(int i=rowStack.size()-1;i>=0;i--){
			// should place this value leaving required cells ahead for other values to come to make column condition true. 
            ans[row++][k-map.get(rowStack.get(i))-1] = rowStack.get(i);
        }
        
        return ans;
    
    }
    
	// toposort dfs along with cycle check (returns false if cycle exists)
    private boolean dfs(int node,boolean[] vis,List<Integer> stack,boolean[] dfsvis){
        vis[node] = true;
        dfsvis[node] = true;
        for(int next : al[node]){
            if(!vis[next]) {
                if(!dfs(next,vis,stack,dfsvis)) return false;
            }else if(dfsvis[next]) return false;
        }
        stack.add(node);
        dfsvis[node] = false;
        return true;
    }
}

Build a Matrix With Conditions LeetCode Solution in Python

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        res = [[0 for _ in range(k)] for _ in range(k)]
        
        # build 2 graphs for row and col independently, count indegrees for each node 
        # a node in each graph is a number between 1 to k
        row_graph, col_graph = defaultdict(set), defaultdict(set)
        row_indegrees, col_indegrees = defaultdict(int), defaultdict(int)
        for i, j in rowConditions:
            # note the input conditions could contain duplicates
            if j not in row_graph[i]:
                row_graph[i].add(j)
                row_indegrees[j] += 1
        for i, j in colConditions:
            if j not in col_graph[i]:
                col_graph[i].add(j)
                col_indegrees[j] += 1
        
        # run topological sort for nodes in row graph
        row_queue, col_queue = deque(), deque()
        row_order, col_order = {}, {}
        row_order_counter, col_order_counter = 0, 0
        row_visited, col_visited = set(), set()
        for i in range(1, k+1):
            # note that numbers did not appear in row conditions also have row_indegree = 0
            if row_indegrees[i] == 0:
                row_queue.append(i)
                row_visited.add(i)
        while row_queue:
            cur = row_queue.popleft()
            row_order[cur] = row_order_counter
            row_order_counter += 1
            for nxt in row_graph[cur]:
                if nxt in row_visited:
                    continue
                row_indegrees[nxt] -= 1
                if row_indegrees[nxt] <= 0:
                    row_visited.add(nxt)
                    row_queue.append(nxt)
        
        # same topological sort for col graph
        for i in range(1, k+1):
            if col_indegrees[i] == 0:
                col_queue.append(i)
                col_visited.add(i)
        while col_queue:
            cur = col_queue.popleft()
            col_order[cur] = col_order_counter
            col_order_counter += 1
            for nxt in col_graph[cur]:
                if nxt in col_visited:
                    continue
                col_indegrees[nxt] -= 1
                if col_indegrees[nxt] <= 0:
                    col_visited.add(nxt)
                    col_queue.append(nxt)

        # check if either row conditions or col conditions contains cycle
        if not (len(row_order) == k and len(col_order) == k):
            return []
        
        # no cycle, build result with row and col independently
        for i in range(1, k+1):
            res[row_order[i]][col_order[i]] = i
        return res
            
        
            
        
Build a Matrix With Conditions LeetCode Solution Review:

In our experience, we suggest you solve this Build a Matrix With Conditions LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Build a Matrix With Conditions LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Build a Matrix With Conditions LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.