#2732
Find a Good Subset of the Matrix
candidate master · 1525 · lc hard +32 · verified · 46.8% accepted · 213 likes · top 31%
Description
Given a 0-indexed binary matrix grid (m x n), a subset of k rows is good if every column sums to at most floor(k / 2). Return the sorted row indices of any good subset, or an empty array if none exists.
Example 1:
Input: grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
Output: [0,1]
Explanation: We can choose the 0th and 1st rows to create a good subset of rows.
The length of the chosen subset is 2.
- The sum of the 0th column is 0 + 0 = 0, which is at most half of the length of the subset.
- The sum of the 1st column is 1 + 0 = 1, which is at most half of the length of the subset.
- The sum of the 2nd column is 1 + 0 = 1, which is at most half of the length of the subset.
- The sum of the 3rd column is 0 + 1 = 1, which is at most half of the length of the subset.
Example 2:
Input: grid = [[0]]
Output: [0]
Explanation: We can choose the 0th row to create a good subset of rows.
The length of the chosen subset is 1.
- The sum of the 0th column is 0, which is at most half of the length of the subset.
Example 3:
Input: grid = [[1,1,1],[1,1,1]]
Output: []
Explanation: It is impossible to choose any subset of rows to create a good subset.
Code
1
2
3