You are given a 0-indexed m x 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 good subsets, 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 or all) rows from grid.
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.
Constraints:
m == grid.lengthn == grid[i].length1 <= m <= 1041 <= n <= 5grid[i][j] is either 0 or 1.Problem Overview: You are given a binary matrix. A subset of rows is considered good if for every column, at most one selected row contains a 1. The task is to return the indices of any valid subset (size ≤ 2) or an empty result if none exists.
Approach 1: Brute Force Subset Enumeration (Time: O(2^n * n * m), Space: O(1))
The direct approach checks every possible subset of rows and verifies whether it satisfies the column constraint. For each subset, iterate through all columns and count how many rows contribute a 1. If any column exceeds one 1, the subset is invalid. Because each subset check scans up to n rows and m columns, the worst-case cost grows exponentially with 2^n. This approach works only for very small inputs but clearly demonstrates the definition of a valid subset and how column conflicts arise.
Approach 2: Greedy Single Row or Minimal Row Pair Selection (Bitmask + Hash Table) (Time: O(n * 2^m) ≈ O(n), Space: O(2^m))
The key observation is that the matrix has at most five columns. That means every row can be compressed into a 5-bit integer mask using bit manipulation. For example, a row like [1,0,1,0,0] becomes the mask 10100. A single row with mask 0 already forms a valid subset because it contains no 1. Otherwise, store each mask and its row index in a hash table. For every row mask, iterate through all possible masks (0–31) and check if (mask & otherMask) == 0. This bitwise AND confirms that the two rows never place 1s in the same column. Once such a pair is found, their indices form a valid answer. Since there are only 32 possible masks, each row performs a constant number of checks, making the approach effectively linear in the number of rows.
This strategy transforms the matrix comparison problem into a compact bitmask compatibility check. Instead of comparing rows column by column, you perform a single bitwise operation. The technique is common in problems involving small fixed-width binary states in array or matrix structures.
Recommended for interviews: The bitmask + hash table approach is what interviewers typically expect. It shows you recognize the small column constraint and convert rows into integer states for fast compatibility checks. Mentioning the brute force subset method first demonstrates understanding of the problem definition, but using bitmasks and constant mask space highlights strong algorithmic optimization skills.
This approach involves generating all possible non-empty subsets of rows and checking if they meet the 'good subset' criteria.
Since n (the number of columns) is small (up to 5), you can afford to use a bitmask to represent each subset of rows for enumeration.
The function find_good_subset iterates through all possible non-empty subsets of the rows, checking each subset with is_good_subset to determine if it meets the criteria. is_good_subset computes the column sums for the given subset of rows and checks if they satisfy the condition of being at most floor(k/2) where k is the number of rows in the subset.
Time Complexity: O(m * 2^m * n), where m is the number of rows and n is the number of columns. This is due to generating all subsets and checking column sums. Space Complexity: O(m) for storing the indices of the current subset.
By focusing on subsets of size 1 or most simply pairs, especially given small column constraints, one could efficiently determine the solution without full subset enumeration.
Consider each single row or pairs of rows and evaluate if they fulfill the condition.
This approach examines individual rows to see if they meet the criteria. If no single row qualifies, it checks pairs of rows. In isGoodRow, a row is 'good' if all its elements are 0. isGoodPair assesses pair compatibility based on column sums.
Java
JavaScript
Time Complexity: O(m^2 * n) because of checking both single and pairs. Space Complexity: O(1).
We can consider the number of rows k chosen for the answer from smallest to largest.
k = 1, the maximum sum of each column is 0. Therefore, there must be a row where all elements are 0, otherwise, the condition cannot be met.k = 2, the maximum sum of each column is 1. There must exist two rows, and the bitwise AND result of these two rows' elements is 0, otherwise, the condition cannot be met.k = 3, the maximum sum of each column is also 1. If the condition for k = 2 is not met, then the condition for k = 3 will definitely not be met either. Therefore, we do not need to consider any case where k > 2 and k is odd.k = 4, the maximum sum of each column is 2. This situation definitely occurs when the condition for k = 2 is not met, meaning that for any two selected rows, there exists at least one column with a sum of 2. When choosing any 2 rows out of 4, there are a total of C_4^2 = 6 ways to choose, so there are at least 6 columns with a sum of 2. Since the number of columns n \le 5, there must be at least one column with a sum greater than 2, so the condition for k = 4 is also not met.k > 4 and k being even, we can draw the same conclusion, that k definitely does not meet the condition.In summary, we only need to consider the cases of k = 1 and k = 2. That is, to check whether there is a row entirely composed of 0s, or whether there exist two rows whose bitwise AND result is 0.
The time complexity is O(m times n + 4^n), and the space complexity is O(2^n). Here, m and n are the number of rows and columns of the matrix, respectively.
| Approach | Complexity |
|---|---|
| Brute Force Subset Enumeration | Time Complexity: O(m * 2^m * n), where m is the number of rows and n is the number of columns. This is due to generating all subsets and checking column sums. Space Complexity: O(m) for storing the indices of the current subset. |
| Greedy Single Row or Minimal Row Pair Selection | Time Complexity: O(m^2 * n) because of checking both single and pairs. Space Complexity: O(1). |
| Case Analysis | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^n * n * m) | O(1) | Useful for understanding the definition of a good subset or when n is extremely small |
| Row Pair Checking (Naive) | O(n^2 * m) | O(1) | Works when rows are limited but still compares columns directly |
| Greedy Bitmask + Hash Table | O(n * 2^m) ≈ O(n) | O(2^m) | Optimal solution when column count is small (≤5). Converts rows to masks and checks compatibility using bitwise AND |
Leetcode BiWeekly contest 106 - Hard - Find a Good Subset of the Matrix • Prakhar Agrawal • 806 views views
Watch 9 more video solutions →Practice Find a Good Subset of the Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor