Watch 10 video solutions for Find a Good Subset of the Matrix, a hard level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by Prakhar Agrawal has 806 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |