aboutsummaryrefslogtreecommitdiff
path: root/build_matrix_conditions.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-07-20 18:26:58 -0600
committerJack Sangdahl <[email protected]>2024-07-20 18:26:58 -0600
commit9737c3c7b514ec7abf057d9cb59297283988bb61 (patch)
tree8409aea981568d4142ecf30c8209e2b4f19e91a0 /build_matrix_conditions.py
parent20318810d2b118ecf1931909cdbd36c87f0951b5 (diff)
downloadleetcode-9737c3c7b514ec7abf057d9cb59297283988bb61.tar.gz
leetcode-9737c3c7b514ec7abf057d9cb59297283988bb61.zip
2392. build a matrix with conditions
Diffstat (limited to 'build_matrix_conditions.py')
-rw-r--r--build_matrix_conditions.py67
1 files changed, 67 insertions, 0 deletions
diff --git a/build_matrix_conditions.py b/build_matrix_conditions.py
new file mode 100644
index 0000000..8f55360
--- /dev/null
+++ b/build_matrix_conditions.py
@@ -0,0 +1,67 @@
+# 2392. Build a Matrix With Conditions
+from collections import deque
+
+"""
+you are givne 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 k' matrix that contains each of the numbers from 1 to 'k'
+exactly once. the remaining cells should 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'. 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'. return any matrix that satisfies these
+conditions.
+"""
+
+
+class Solution(object):
+ def buildMatrix(self, k, rowConditions, colConditions):
+ """
+ :type k: int
+ :type rowConditions: List[List[int]]
+ :type colConditions: List[List[int]]
+ :rtype: List[List[int]]
+ """
+
+ def helper(a):
+ next, in_deg = [set() for _ in range(k)], [0] * k
+ dq, res = deque(), []
+ a = set([tuple(i) for i in a])
+ for i, j in a:
+ next[i - 1].add(j - 1)
+ in_deg[j - 1] += 1
+ for i in range(k):
+ if in_deg[i] == 0:
+ dq.append(i)
+ while dq:
+ curr = dq.popleft()
+ res.append(curr)
+ for candidate in next[curr]:
+ in_deg[candidate] -= 1
+ if in_deg[candidate] == 0:
+ dq.append(candidate)
+ return res if len(res) == k else []
+
+ a1, a2 = helper(rowConditions), helper(colConditions)
+ if not a1 or not a2:
+ return []
+ ans = [[0] * k for _ in range(k)]
+ for i in range(k):
+ ans[a1.index(i)][a2.index(i)] = i + 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.buildMatrix(
+ k=3, rowConditions=[[1, 2], [3, 2]], colConditions=[[2, 1], [3, 2]]
+ )
+ )
+ print(
+ obj.buildMatrix(
+ k=3, rowConditions=[[1, 2], [2, 3], [3, 1], [2, 3]], colConditions=[[2, 1]]
+ )
+ )