# Find a Good Subset of the Matrix
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-a-good-subset-of-the-matrix)
Canonical: https://scaleengineer.com/dsa/problems/find-a-good-subset-of-the-matrix
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table, Matrix
---
## 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 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`.

# Approaches
## Brute-Force Enumeration of All Subsets
This approach involves generating every possible non-empty subset of rows from the given matrix and, for each subset, checking if it satisfies the "good subset" criteria. A subset is good if, for every column, the sum of its elements is no more than half the number of rows in the subset.
**Time:** O(2^m * m * n). There are `2^m` subsets. For each subset, we iterate up to `m` rows and `n` columns to check the condition. This is computationally infeasible for the given constraints. · **Space:** O(m) to store the indices of the current subset being evaluated.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find a solution if one exists.
**Cons:** Extremely high time complexity, `O(2^m * m * n)`, which is not feasible for the given constraints where `m` can be up to 10,000.
### Explanation
The most straightforward way to solve this problem is to exhaustively check all possibilities. We can represent a subset of rows using a bitmask of length `m`. Each bit in the mask corresponds to a row, and if the bit is set, the row is included in the subset. We iterate through all possible masks from 1 to `2^m - 1` (excluding the empty set). For each mask, we form the corresponding subset of rows and verify if it's a "good" subset by checking the sum of each column against the condition. The first good subset we find is a valid answer.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Iterate through all 2^m - 1 non-empty subsets of rows
        for (int i = 1; i < (1 << m); i++) {
            List<Integer> subsetIndices = new ArrayList<>();
            int k = 0; // Size of the subset
            for (int j = 0; j < m; j++) {
                // Check if the j-th row is in the current subset
                if ((i & (1 << j)) != 0) {
                    subsetIndices.add(j);
                    k++;
                }
            }

            if (isGood(grid, subsetIndices, k, n)) {
                return subsetIndices; // Found a good subset
            }
        }

        return new ArrayList<>(); // No good subset found
    }

    private boolean isGood(int[][] grid, List<Integer> subset, int k, int n) {
        if (k == 0) {
            return false;
        }
        for (int j = 0; j < n; j++) {
            int colSum = 0;
            for (int rowIndex : subset) {
                colSum += grid[rowIndex][j];
            }
            if (colSum > k / 2) {
                return false; // Condition failed for this column
            }
        }
        return true; // All columns satisfy the condition
    }
}
```
### Algorithm
- Generate all `2^m - 1` non-empty subsets of row indices. This can be done by iterating a counter from 1 to `2^m - 1` and using its binary representation to select rows.
- For each subset of size `k`:
  - For each column `j` from `0` to `n-1`, calculate the sum of its elements over the rows in the subset.
  - If the sum for any column `j` is greater than `floor(k/2)`, this subset is not good. Move to the next subset.
  - If all column sums satisfy the condition, a good subset has been found. Return its row indices, sorted in ascending order.
- If the loop finishes without finding any good subset, it means none exists. Return an empty array.

## Optimized Approach using Bitmasking and Pairwise Check
This optimized approach leverages the small constraint on `n` (the number of columns, `n <= 5`). Each row can be represented as an integer bitmask. The solution is based on the key insight that if any good subset exists, then a good subset of size 1 (an all-zero row) or size 2 (two rows whose bitmasks have a bitwise AND of 0) must also exist. This dramatically reduces the search space from all `2^m` subsets to just subsets of size 1 and 2.
**Time:** O(m*n + (2^n)^2). It takes `O(m*n)` to iterate through the grid and compute masks. Then, it takes `O((2^n)^2)` to check all pairs of unique masks. Since `n <= 5`, `2^n` is at most 32, making the second term a small constant (`32*32=1024`). The overall complexity is dominated by the grid traversal, making it `O(m*n)`. · **Space:** O(2^n). We use a map to store an index for each unique mask. Since `n <= 5`, the number of possible masks is at most 32. This is effectively constant space.
**Pros:** Highly efficient with a time complexity linear in the size of the grid.; Uses constant extra space because `n` is very small.; Simple to implement once the key insight is understood.
**Cons:** The correctness relies on the non-trivial property that the existence of any good subset implies the existence of one of size 1 or 2.
### Explanation
We can significantly improve efficiency by focusing our search. A subset of size 1 is good only if it's an all-zero row. A subset of size 2, with rows `i` and `p`, is good if their combined column sums are at most 1. This is equivalent to `(mask(row_i) & mask(row_p)) == 0`.

It can be proven that if a good subset of any size `k` exists, then a good subset of size 1 or 2 must also exist. Therefore, we only need to check for these two simple cases.

The algorithm first iterates through the grid to find an all-zero row. If found, we are done. If not, we use a hash map to store the unique row patterns (as bitmasks) and their first-seen row indices. Since `n <= 5`, there are at most `2^5 = 32` unique masks. After populating the map, we check every pair of unique masks. If we find a pair whose bitwise AND is zero, we have found a good subset of size 2.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // Map to store a representative index for each mask found
        Map<Integer, Integer> maskToIndex = new HashMap<>();

        for (int i = 0; i < m; i++) {
            int currentMask = 0;
            for (int j = 0; j < n; j++) {
                currentMask |= grid[i][j] << j;
            }

            // Case 1: Good subset of size 1
            if (currentMask == 0) {
                return Arrays.asList(i);
            }

            maskToIndex.put(currentMask, i);
        }

        // Case 2: Good subset of size 2
        for (int mask1 : maskToIndex.keySet()) {
            for (int mask2 : maskToIndex.keySet()) {
                if ((mask1 & mask2) == 0) {
                    int index1 = maskToIndex.get(mask1);
                    int index2 = maskToIndex.get(mask2);
                    // The problem asks for any good subset, so we can return the first one we find.
                    // Sorting is required for the output format.
                    return index1 < index2 ? Arrays.asList(index1, index2) : Arrays.asList(index2, index1);
                }
            }
        }

        return new ArrayList<>(); // No good subset found
    }
}
```
### Algorithm
- The core idea is that if any good subset exists, a good subset of size 1 or 2 must also exist.
- **Check for size 1:** A single row `i` is a good subset if it contains all zeros. The condition is `sum <= floor(1/2) = 0`.
- **Check for size 2:** A pair of rows `i` and `p` is a good subset if for every column, `grid[i][j] + grid[p][j] <= floor(2/2) = 1`. This is true if and only if the bitwise AND of their corresponding masks is 0.
- **Algorithm Steps:**
  1. Create a map to store the first seen index for each unique row mask (`mask -> rowIndex`).
  2. Iterate through each row `i` of the grid.
  3. Convert the row to its integer bitmask representation.
  4. If the mask is 0, we've found a size-1 good subset. Return `[i]` immediately.
  5. Store the mask and index `i` in the map.
  6. After iterating through all rows (if no all-zero row was found), iterate through all pairs of unique masks present in the map.
  7. For any pair of masks `(m1, m2)` such that `(m1 & m2) == 0`, retrieve their original indices and return them as the answer, sorted.
  8. If no such pair is found, no good subset of size 1 or 2 exists, which implies no good subset of any size exists. Return an empty array.

# Solutions
### Java

```java
class Solution { public List < Integer > goodSubsetofBinaryMatrix ( int [][] grid ) { Map < Integer , Integer > g = new HashMap <>(); for ( int i = 0 ; i < grid . length ; ++ i ) { int mask = 0 ; for ( int j = 0 ; j < grid [ 0 ]. length ; ++ j ) { mask |= grid [ i ][ j ] << j ; } if ( mask == 0 ) { return List . of ( i ); } g . put ( mask , i ); } for ( var e1 : g . entrySet ()) { for ( var e2 : g . entrySet ()) { if (( e1 . getKey () & e2 . getKey ()) == 0 ) { int i = e1 . getValue (), j = e2 . getValue (); return List . of ( Math . min ( i , j ), Math . max ( i , j )); } } } return List . of (); } }
```

### CPP

```cpp
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 {}; } };
```

### Python

```python
class Solution : def goodSubsetofBinaryMatrix ( self , grid : List [ List [ int ]]) -> List [ int ]: g = {} for i , row in enumerate ( grid ): mask = 0 for j , x in enumerate ( row ): mask |= x << j if mask == 0 : return [ i ] g [ mask ] = i for a , i in g . items (): for b , j in g . items (): if ( a & b ) == 0 : return sorted ([ i , j ]) return []
```