Skip to main content
Talentd

Find a Good Subset of the Matrix - Solution & Explanation

HardArrayHash TableBit ManipulationMatrix20 min read
Practice this problem

Problem Statement

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.length
  • n == grid[i].length
  • 1 <= m <= 104
  • 1 <= n <= 5
  • grid[i][j] is either 0 or 1.

Approach Overview

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 1: Brute Force Subset Enumeration

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.

Code

PythonC#

Python

C#

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Single Row or Minimal Row Pair Selection

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(m^2 * n) because of checking both single and pairs. Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Case Analysis

We can consider the number of rows k chosen for the answer from smallest to largest.

  • If 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.
  • If 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.
  • If 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.
  • If 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.
  • For 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subset EnumerationO(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 TableO(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

Video Solution

Leetcode BiWeekly contest 106 - Hard - Find a Good Subset of the Matrix • Prakhar Agrawal • 806 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Find a Good Subset of the Matrix easy or hard?
The problem is rated Hard on LeetCode because the optimal idea is not obvious at first glance. Once you recognize that the number of columns is small, the solution becomes straightforward using bit manipulation and hash table lookup. Identifying that constraint is the key insight.
Find a Good Subset of the Matrix Python/Java solution
Most implementations follow the same structure: convert rows to bitmasks, store masks in a dictionary or map, and test compatibility using bitwise AND. Python commonly uses a dictionary for mask lookups, while Java uses a HashMap. Both achieve O(n) time because the mask space is limited to 32 possibilities.
How to solve Find a Good Subset of the Matrix in O(n)?
Convert each row into a binary bitmask and store it in a hash table with its index. If a row has mask 0, it forms a valid subset by itself. Otherwise check all possible masks and find one where (mask & otherMask) == 0, meaning the rows never share a column with value 1. Because only 32 masks exist, each row performs a constant number of checks, giving near O(n) time.
What is the best approach for Find a Good Subset of the Matrix?
The most efficient approach converts each row into a bitmask and uses a hash table to track seen masks. Because the matrix has at most five columns, there are only 32 possible masks. Checking whether two rows are compatible reduces to a single bitwise AND operation. This produces an O(n) time solution with O(2^m) space.
Is Find a Good Subset of the Matrix asked at Google/Amazon/Meta?
Problems involving bitmasking and small-dimension matrices frequently appear in interviews at companies like Google, Amazon, and Meta. The pattern of compressing rows into bitmasks and checking compatibility using bitwise operations is a common interview technique.
What data structure is used in Find a Good Subset of the Matrix?
The optimal solution uses a hash table (or dictionary) combined with bitmask integers. The hash table maps each mask to the index of the row where it appears. Bitwise operations allow constant-time compatibility checks between two rows.
What is the time complexity of Find a Good Subset of the Matrix?
The optimal bitmask solution runs in O(n * 2^m) time, where n is the number of rows and m ≤ 5 is the number of columns. Since 2^5 = 32, the algorithm behaves like O(n) in practice. Space complexity is O(2^m) to store previously seen row masks.

Ready to solve this problem?

Practice Find a Good Subset of the Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays