aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-19 21:43:00 -0700
committerJack Sangdahl <[email protected]>2025-01-19 21:43:00 -0700
commit9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb (patch)
tree2233a991d64e50f0029cbce6a1be74d8b41c7c4b
parent9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a (diff)
downloadleetcode-9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb.tar.gz
leetcode-9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb.zip
2661. first completely painted row or column
-rw-r--r--first_completely_painted_rc.c66
-rw-r--r--first_completely_painted_rc.py39
2 files changed, 105 insertions, 0 deletions
diff --git a/first_completely_painted_rc.c b/first_completely_painted_rc.c
new file mode 100644
index 0000000..fc4599b
--- /dev/null
+++ b/first_completely_painted_rc.c
@@ -0,0 +1,66 @@
+// 2661. First Completely Painted Row or Column
+#include "leetcode.h"
+
+/*
+ * 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'.
+ */
+
+typedef struct {
+ UT_hash_handle hh;
+ int val;
+ int row;
+ int col;
+} hElem;
+
+int firstCompleteIndex(int *arr, int arrSize, int **mat, int matSize,
+ int *matColSize) {
+ int m = matSize, n = matColSize[0];
+ int *row_cnt = (int *)calloc(m, sizeof(int));
+ int *col_cnt = (int *)calloc(n, sizeof(int));
+ hElem *map = NULL, *tmp;
+ for (int r = 0; r < m; r++)
+ for (int c = 0; c < n; c++) {
+ HASH_FIND_INT(map, &mat[r][c], tmp);
+ if (!tmp) {
+ tmp = (hElem *)malloc(sizeof(hElem));
+ tmp->val = mat[r][c];
+ tmp->row = r;
+ tmp->col = c;
+ HASH_ADD_INT(map, val, tmp);
+ }
+ }
+ for (int i = 0; i < arrSize; i++) {
+ int r = 0, c = 0;
+ HASH_FIND_INT(map, &arr[i], tmp);
+ if (tmp) {
+ r = tmp->row;
+ c = tmp->col;
+ }
+ ++row_cnt[r];
+ ++col_cnt[c];
+ if (n == row_cnt[r] || m == col_cnt[c])
+ return i;
+ }
+ free(row_cnt);
+ free(col_cnt);
+ return -1;
+}
+
+int main() {
+ int a1[] = {1, 3, 4, 2}, m1i[2][2] = {{1, 4}, {2, 3}};
+ int a2[] = {2, 8, 7, 4, 1, 3, 5, 6, 9},
+ m2i[3][3] = {{3, 2, 5}, {1, 4, 6}, {8, 7, 9}};
+ struct two_d_arr m1, m2;
+ two_d_arr_init(&m1, ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i);
+ two_d_arr_init(&m2, ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i);
+ printf("%d\n", firstCompleteIndex(a1, ARRAY_SIZE(a1), m1.arr, m1.row_size,
+ m1.col_size)); // expect: 2
+ printf("%d\n", firstCompleteIndex(a2, ARRAY_SIZE(a2), m2.arr, m2.row_size,
+ m2.col_size)); // expect: 3
+ two_d_arr_free(&m1);
+ two_d_arr_free(&m2);
+}
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]]
+ )
+ )