diff options
author | Jack Sangdahl <[email protected]> | 2024-07-20 18:26:58 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-20 18:26:58 -0600 |
commit | 9737c3c7b514ec7abf057d9cb59297283988bb61 (patch) | |
tree | 8409aea981568d4142ecf30c8209e2b4f19e91a0 /build_matrix_conditions.py | |
parent | 20318810d2b118ecf1931909cdbd36c87f0951b5 (diff) | |
download | leetcode-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.py | 67 |
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]] + ) + ) |