Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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
rowConditionsof sizenwhererowConditions[i] = [abovei, belowi], and - a 2D integer array
colConditionsof sizemwherecolConditions[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
aboveishould appear in a row that is strictly above the row at which the numberbelowiappears for allifrom0ton - 1. - The number
leftishould appear in a column that is strictly left of the column at which the numberrightiappears for allifrom0tom - 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 <= 4001 <= rowConditions.length, colConditions.length <= 104rowConditions[i].length == colConditions[i].length == 21 <= abovei, belowi, lefti, righti <= kabovei != belowilefti != 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
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 >>
