diff options
author | Jack Sangdahl <[email protected]> | 2024-12-28 11:58:43 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-28 11:58:43 -0700 |
commit | 54c2ee3c2fdbddd44f8ebddd720234d9b0e36e5d (patch) | |
tree | e263eea163076a72835784606b9e816eaa958a97 | |
parent | be2dd2d507ad02c2ebfb3e371cfda1d4612de271 (diff) | |
download | leetcode-54c2ee3c2fdbddd44f8ebddd720234d9b0e36e5d.tar.gz leetcode-54c2ee3c2fdbddd44f8ebddd720234d9b0e36e5d.zip |
2732. find a good subset of the matrix
-rw-r--r-- | find_good_subset_matrix.c | 89 | ||||
-rw-r--r-- | find_good_subset_matrix.py | 38 |
2 files changed, 127 insertions, 0 deletions
diff --git a/find_good_subset_matrix.c b/find_good_subset_matrix.c new file mode 100644 index 0000000..aadf5ce --- /dev/null +++ b/find_good_subset_matrix.c @@ -0,0 +1,89 @@ +// 2732. Find a Good Subset of the Matrix +#include "leetcode.h" + +/* + * you are given a 0-indexed 'm * n' binary matrix 'grid'. let us call a + * non-empty subset of rows good if the sum of each column of the subset is at + * most half of the length of the subset. more formally, if the length of the + * chosen subset of rows is 'k', then the sum of each column should be at most + * 'floor(k / 2)'. return an integer array that contains row indices of a good + * subset sorted in ascending order. if there are multiple answers, you can + * return any of them. if there are no good subsets, return an empty array. a + * subset of rows of the matrix 'grid' is any matrix that can be obtained by + * deleting some (possibly none) rows from 'grid' + */ + +static uint encode(const int *row, int rowSize) { + uint x = 0; + for (int i = 0; i < rowSize; ++i) { + if (!row[i]) + continue; + x |= 1 << i; + } + return x; +} + +int *goodSubsetofBinaryMatrix(int **grid, int gridSize, int *gridColSize, + int *returnSize) { + const int n = 1 << *gridColSize; + int *idx = (int *)malloc(n * sizeof(int)); + memset(idx, -1, n * sizeof(int)); + for (int i = gridSize - 1; i >= 0; --i) + idx[encode(grid[i], gridSize)] = i; + if (idx[0] != -1) { + *returnSize = 1; + int *ans = (int *)malloc(*returnSize * sizeof(int)); + ans[0] = idx[0]; + free(idx); + return ans; + } + for (int a = 1; a < n; ++a) { + if (idx[a] == -1) + continue; + for (int b = a + 1; b < n; ++b) { + if (idx[b] == -1) + continue; + if (!(a & b)) { + int row_a = idx[a]; + int row_b = idx[b]; + free(idx); + *returnSize = 2; + int *ans = (int *)malloc(*returnSize * sizeof(int)); + ans[0] = fmin(row_a, row_b); + ans[1] = fmax(row_a, row_b); + return ans; + } + } + } + *returnSize = 0; + free(idx); + return NULL; +} + +int main() { + int g1i[3][4] = {{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 1, 1}}, rs1; + int g2i[1][1] = {{0}}, rs2; + int g3i[2][3] = {{1, 1, 1}, {1, 1, 1}}, rs3; + struct two_d_arr g1, g2, g3; + two_d_arr_init(&g1, 3, 4, g1i); + two_d_arr_init(&g2, 1, 1, g2i); + two_d_arr_init(&g3, 2, 3, g3i); + int *gsobm1 = + goodSubsetofBinaryMatrix(g1.arr, g1.row_size, g1.col_size, &rs1); + int *gsobm2 = + goodSubsetofBinaryMatrix(g2.arr, g2.row_size, g2.col_size, &rs2); + int *gsobm3 = + goodSubsetofBinaryMatrix(g3.arr, g3.row_size, g3.col_size, &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", gsobm1[i]); // expect: 0 1 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", gsobm2[i]); // expect: 0 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%d ", gsobm3[i]); // expect: null + printf("\n"); + free(gsobm1), two_d_arr_free(&g1); + free(gsobm2), two_d_arr_free(&g2); + free(gsobm3), two_d_arr_free(&g3); +} diff --git a/find_good_subset_matrix.py b/find_good_subset_matrix.py new file mode 100644 index 0000000..cd6d3a1 --- /dev/null +++ b/find_good_subset_matrix.py @@ -0,0 +1,38 @@ +# 2732. Find a Good Subset of the Matrix + +""" +you are given a 0-indexed 'm n' binary matrix 'grid'. let us call a +non-empty subset of rows good if the sum of each column of the subset is at +most half of the length of the subset. more formally, if the length of the +chosen subset of rows is 'k', then the sum of each column should be at most +'floor(k / 2)'. return an integer array that contains row indices of a good +subset sorted in ascending order. if there are multiple answers, you can +return any of them. if there are no good subsets, return an empty array. a +subset of rows of the matrix 'grid' is any matrix that can be obtained by +deleting some (possibly none) rows from 'grid' +""" + + +class Solution(object): + def goodSubsetofBinaryMatrix(self, grid): + """ + :type grid: List[List[int]] + :rtype: List[int] + """ + if len(grid) == 1: + return [0] if all(num == 0 for num in grid[0]) else [] + d = {} + for r, row in enumerate(grid): + num = sum(cell << c for c, cell in enumerate(row)) + for i in range(32): + if (i & num) == 0 and i in d: + return [d[i], r] + d.setdefault(num, r) + return [] + + +if __name__ == "__main__": + obj = Solution() + print(obj.goodSubsetofBinaryMatrix(grid=[[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 1, 1]])) + print(obj.goodSubsetofBinaryMatrix(grid=[[0]])) + print(obj.goodSubsetofBinaryMatrix(grid=[[1, 1, 1], [1, 1, 1]])) |