aboutsummaryrefslogtreecommitdiff
path: root/first_completely_painted_rc.py
diff options
context:
space:
mode:
Diffstat (limited to 'first_completely_painted_rc.py')
-rw-r--r--first_completely_painted_rc.py39
1 files changed, 39 insertions, 0 deletions
diff --git a/first_completely_painted_rc.py b/first_completely_painted_rc.py
new file mode 100644
index 0000000..fd65ef2
--- /dev/null
+++ b/first_completely_painted_rc.py
@@ -0,0 +1,39 @@
+# 2661. First Completely Painted Row or Column
+
+"""
+you are given a 0-indexed integer array 'arr', and an 'm x n' integer array
+'matrix'. 'arr' and 'mat' bboth contain all the integers in the range '[1, m
+n]'. go through each index 'i' in 'arr' starting from index 0, and paint
+the cell in 'mat' containing the integer 'arr[i]'. return the smallest index
+'i' at which either a row or a column will bbe completely painted in 'mat'.
+"""
+
+
+class Solution(object):
+ def firstCompleteIndex(self, arr, mat):
+ """
+ :type arr: List[int]
+ :type mat: List[List[int]]
+ :rtype: int
+ """
+ m, n = len(mat), len(mat[0])
+ map = {mat[r][c]: (r, c) for r in range(m) for c in range(n)}
+ row_cnt = [n] * m
+ col_cnt = [m] * n
+ for idx, val in enumerate(arr):
+ r, c = map[val]
+ row_cnt[r] -= 1
+ col_cnt[c] -= 1
+ if row_cnt[r] == 0 or col_cnt[c] == 0:
+ return idx
+ return -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.firstCompleteIndex(arr=[1, 3, 4, 2], mat=[[1, 4], [2, 3]]))
+ print(
+ obj.firstCompleteIndex(
+ arr=[2, 8, 7, 4, 1, 3, 5, 6, 9], mat=[[3, 2, 5], [1, 4, 6], [8, 7, 9]]
+ )
+ )