Problem Description
You are given a 0-indexed m x n binary matrix grid. A non-empty subset of rows is called good if the sum of each column of the subset is at most half of the length of the subset. Return an integer array that contains row indices of a good subset sorted in ascending order. If there are multiple good subsets, you can return any of them. If there are no good subsets, return an empty array.
Key Insights
- A subset of rows must satisfy the condition that for a subset of length k, the sum of each column must be at most floor(k / 2).
- The maximum number of rows can be 10,000, but the number of columns is limited to 5, which allows for efficient checking of conditions.
- We can use bit manipulation to explore different combinations of rows due to the small number of columns.
Space and Time Complexity
Time Complexity: O(m * n) - We need to potentially check all rows and their contributions to each column. Space Complexity: O(m) - To store the indices of the selected rows.
Solution
To solve the problem, we will iterate through each row of the grid, maintaining a count of the number of 1's in each column. We will then check if adding a row to our current subset keeps the sums of each column within the acceptable limits. The algorithm can use a greedy approach to build a good subset by adding rows until the condition fails.