diff options
author | Jack Sangdahl <[email protected]> | 2025-01-19 21:43:00 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-19 21:43:00 -0700 |
commit | 9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb (patch) | |
tree | 2233a991d64e50f0029cbce6a1be74d8b41c7c4b | |
parent | 9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a (diff) | |
download | leetcode-9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb.tar.gz leetcode-9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb.zip |
2661. first completely painted row or column
-rw-r--r-- | first_completely_painted_rc.c | 66 | ||||
-rw-r--r-- | first_completely_painted_rc.py | 39 |
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]] + ) + ) |