diff options
Diffstat (limited to 'find_good_subset_matrix.py')
-rw-r--r-- | find_good_subset_matrix.py | 38 |
1 files changed, 38 insertions, 0 deletions
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]])) |