2732. Find a Good Subset of the Matrix - Solution

The problem

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 0^th and 1^st rows to create a good subset of rows.
The length of the chosen subset is 2.
- The sum of the 0^th column is 0 + 0 = 0, which is at most half of the length of the subset.
- The sum of the 1^st column is 1 + 0 = 1, which is at most half of the length of the subset.
- The sum of the 2^nd column is 1 + 0 = 1, which is at most half of the length of the subset.
- The sum of the 3^rd 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 0^th row to create a good subset of rows.
The length of the chosen subset is 1.
- The sum of the 0^th 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 <= 10⁴
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.

Python

def find_good_subset(grid):
    from itertools import combinations
    m, n = len(grid), len(grid[0])
    for size in range(1, m+1):
        for subset in combinations(range(m), size):
            if is_good_subset(grid, subset, n):
                return list(subset)
    return []


def is_good_subset(grid, subset, n):
    cols = [0] * n
    k = len(subset)
    for i in subset:
        for j in range(n):
            cols[j] += grid[i][j]
    return all(c <= k // 2 for c in cols)

# Example usage
grid = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 1, 1]]
print(find_good_subset(grid))  # Output: [0, 1]

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public List<int> FindGoodSubset(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        for (int size = 1; size <= m; size++) {
            foreach (var subset in GetCombinations(m, size)) {
                if (IsGoodSubset(grid, subset, n)) {
                    return subset.ToList();
                }
            }
        }
        return new List<int>();
    }

    private bool IsGoodSubset(int[][] grid, List<int> subset, int n) {
        int[] cols = new int[n];
        int k = subset.Count;
        foreach (int i in subset) {
            for (int j = 0; j < n; j++) {
                cols[j] += grid[i][j];
            }
        }
        return cols.All(c => c <= k / 2);
    }

    private IEnumerable<List<int>> GetCombinations(int m, int size) {
        return Enumerable.Range(0, m).Combinations(size);
    }
}

public static class EnumerableExtensions {
    public static IEnumerable<List<int>> Combinations(this IEnumerable<int> elements, int k) {
        if (k == 0) return new List<List<int>> { new List<int>() };
        return elements.SelectMany((e, i) => elements.Skip(i + 1).Combinations(k - 1).Select(c => (new List<int> { e }).Concat(c).ToList()));
    }
}

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.

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.

Java

import java.util.*;

public class Solution {
    public List<Integer> findGoodSubset(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // Check single row subsets
        for (int i = 0; i < m; i++) {
            if (isGoodRow(grid[i], n)) {
                return Collections.singletonList(i);
            }
        }
        // Check pairs
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                if (isGoodPair(grid[i], grid[j], n)) {
                    return Arrays.asList(i, j);
                }
            }
        }
        return Collections.emptyList();
    }

    private boolean isGoodRow(int[] row, int n) {
        return Arrays.stream(row).allMatch(value -> value == 0);
    }

    private boolean isGoodPair(int[] row1, int[] row2, int n) {
        for (int j = 0; j < n; j++) {
            if (row1[j] + row2[j] > 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 1, 1}};
        System.out.println(sol.findGoodSubset(grid));  // Output: [0, 1]
    }
}

JavaScript

function findGoodSubset(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Check for single good row
    for (let i = 0; i < m; i++) {
        if (grid[i].every(value => value === 0)) {
            return [i];
        }
    }
    
    // Check for good pair
    for (let i = 0; i < m; i++) {
        for (let j = i + 1; j < m; j++) {
            if (isGoodPair(grid[i], grid[j])) {
                return [i, j];
            }
        }
    }
    return [];
}

function isGoodPair(row1, row2) {
    return row1.every((value, index) => value + row2[index] <= 1);
}

// Example usage
const grid = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 1, 1]];
console.log(findGoodSubset(grid));  // Output: [0, 1]

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.

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.

C++

class Solution {
public:
    vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
        unordered_map<int, int> g;
        for (int i = 0; i < grid.size(); ++i) {
            int mask = 0;
            for (int j = 0; j < grid[0].size(); ++j) {
                mask |= grid[i][j] << j;
            }
            if (mask == 0) {
                return {i};
            }
            g[mask] = i;
        }
        for (auto& [a, i] : g) {
            for (auto& [b, j] : g) {
                if ((a & b) == 0) {
                    return {min(i, j), max(i, j)};
                }
            }
        }
        return {};
    }
};

TypeScript

function goodSubsetofBinaryMatrix(grid: number[][]): number[] {
    const g: Map<number, number> = new Map();
    const m = grid.length;
    const n = grid[0].length;
    for (let i = 0; i < m; ++i) {
        let mask = 0;
        for (let j = 0; j < n; ++j) {
            mask |= grid[i][j] << j;
        }
        if (!mask) {
            return [i];
        }
        g.set(mask, i);
    }
    for (const [a, i] of g.entries()) {
        for (const [b, j] of g.entries()) {
            if ((a & b) === 0) {
                return [Math.min(i, j), Math.max(i, j)];
            }
        }
    }
    return [];
}

func goodSubsetofBinaryMatrix(grid [][]int) []int {
	g := map[int]int{}
	for i, row := range grid {
		mask := 0
		for j, x := range row {
			mask |= x << j
		}
		if mask == 0 {
			return []int{i}
		}
		g[mask] = i
	}
	for a, i := range g {
		for b, j := range g {
			if a&b == 0 {
				return []int{min(i, j), max(i, j)}
			}
		}
	}
	return []int{}
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn good_subsetof_binary_matrix(grid: Vec<Vec<i32>>) -> Vec<i32> {
        let mut g: HashMap<i32, i32> = HashMap::new();
        for (i, row) in grid.iter().enumerate() {
            let mut mask = 0;
            for (j, &x) in row.iter().enumerate() {
                mask |= x << j;
            }
            if mask == 0 {
                return vec![i as i32];
            }
            g.insert(mask, i as i32);
        }

        for (&a, &i) in g.iter() {
            for (&b, &j) in g.iter() {
                if (a & b) == 0 {
                    return vec![i.min(j), i.max(j)];
                }
            }
        }

        vec![]
    }
}

Try this approach in the editor

Complexity comparison

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	–

Complexity 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

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.

Find a Good Subset of the Matrix solution and explanation

The problem

Approach overview

Approach 1: Brute Force Subset Enumeration

Approach 2: Greedy Single Row or Minimal Row Pair Selection

Approach 3: Case Analysis

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find a Good Subset of the Matrix solution and explanation

The problem

Approach overview

Approach 1: Brute Force Subset Enumeration

Approach 2: Greedy Single Row or Minimal Row Pair Selection

Approach 3: Case Analysis

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems