aboutsummaryrefslogtreecommitdiff
path: root/find_good_subset_matrix.py
diff options
context:
space:
mode:
Diffstat (limited to 'find_good_subset_matrix.py')
-rw-r--r--find_good_subset_matrix.py38
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]]))