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 inascending 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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5

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

1
2
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^4
  • 1 <= n <= 5
  • grid[i][j] is either 0 or 1.

Solution

Method 1 – Bitmasking and Hashing

Intuition

Each row in the matrix can be represented as a bitmask. The problem asks for a non-empty subset of rows such that, for each column, the sum of 1s is at most half the subset size. For binary matrices, this is only possible if no column has more than half 1s, which is only possible if the subset contains at most one 1 per column. Thus, we can look for either a single row of all 0s, or a pair of rows with no overlapping 1s (i.e., their bitmasks have no common set bits).

Approach

  1. Convert each row to an integer bitmask.
  2. If any row is all 0s, return its index as a singleton subset.
  3. Use a hash map to store the indices of each unique bitmask.
  4. For each pair of different bitmasks, if their bitwise AND is 0, return their indices (sorted).
  5. If no such subset exists, return an empty array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        unordered_map<int, int> mask2idx;
        for (int i = 0; i < m; ++i) {
            int mask = 0;
            for (int j = 0; j < n; ++j) mask |= (grid[i][j] << j);
            if (mask == 0) return {i};
            if (mask2idx.count(mask)) continue;
            mask2idx[mask] = i;
        }
        for (auto& [mask1, i] : mask2idx) {
            for (auto& [mask2, j] : mask2idx) {
                if (i < j && (mask1 & mask2) == 0)
                    return {i, j};
            }
        }
        return {};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func goodSubsetofBinaryMatrix(grid [][]int) []int {
    m, n := len(grid), len(grid[0])
    mask2idx := map[int]int{}
    for i := 0; i < m; i++ {
        mask := 0
        for j := 0; j < n; j++ {
            mask |= grid[i][j] << j
        }
        if mask == 0 {
            return []int{i}
        }
        if _, ok := mask2idx[mask]; !ok {
            mask2idx[mask] = i
        }
    }
    for mask1, i := range mask2idx {
        for mask2, j := range mask2idx {
            if i < j && mask1&mask2 == 0 {
                return []int{i, j}
            }
        }
    }
    return nil
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Map<Integer, Integer> mask2idx = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int mask = 0;
            for (int j = 0; j < n; j++) mask |= (grid[i][j] << j);
            if (mask == 0) return List.of(i);
            mask2idx.putIfAbsent(mask, i);
        }
        for (var e1 : mask2idx.entrySet()) {
            for (var e2 : mask2idx.entrySet()) {
                if (e1.getValue() < e2.getValue() && (e1.getKey() & e2.getKey()) == 0)
                    return List.of(e1.getValue(), e2.getValue());
            }
        }
        return List.of();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun goodSubsetofBinaryMatrix(grid: Array<IntArray>): List<Int> {
        val m = grid.size
        val n = grid[0].size
        val mask2idx = mutableMapOf<Int, Int>()
        for (i in 0 until m) {
            var mask = 0
            for (j in 0 until n) mask = mask or (grid[i][j] shl j)
            if (mask == 0) return listOf(i)
            mask2idx.putIfAbsent(mask, i)
        }
        for ((mask1, i) in mask2idx) {
            for ((mask2, j) in mask2idx) {
                if (i < j && (mask1 and mask2) == 0) return listOf(i, j)
            }
        }
        return emptyList()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def goodSubsetofBinaryMatrix(self, grid: list[list[int]]) -> list[int]:
        m, n = len(grid), len(grid[0])
        mask2idx = {}
        for i in range(m):
            mask = 0
            for j in range(n):
                mask |= grid[i][j] << j
            if mask == 0:
                return [i]
            if mask not in mask2idx:
                mask2idx[mask] = i
        for mask1, i in mask2idx.items():
            for mask2, j in mask2idx.items():
                if i < j and (mask1 & mask2) == 0:
                    return [i, j]
        return []
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn good_subset_of_binary_matrix(grid: Vec<Vec<i32>>) -> Vec<i32> {
        let m = grid.len();
        let n = grid[0].len();
        let mut mask2idx = std::collections::HashMap::new();
        for i in 0..m {
            let mut mask = 0;
            for j in 0..n {
                mask |= grid[i][j] << j;
            }
            if mask == 0 {
                return vec![i as i32];
            }
            mask2idx.entry(mask).or_insert(i);
        }
        for (&mask1, &i) in &mask2idx {
            for (&mask2, &j) in &mask2idx {
                if i < j && (mask1 & mask2) == 0 {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    goodSubsetofBinaryMatrix(grid: number[][]): number[] {
        const m = grid.length, n = grid[0].length;
        const mask2idx = new Map<number, number>();
        for (let i = 0; i < m; i++) {
            let mask = 0;
            for (let j = 0; j < n; j++) mask |= grid[i][j] << j;
            if (mask === 0) return [i];
            if (!mask2idx.has(mask)) mask2idx.set(mask, i);
        }
        for (const [mask1, i] of mask2idx) {
            for (const [mask2, j] of mask2idx) {
                if (i < j && (mask1 & mask2) === 0) return [i, j];
            }
        }
        return [];
    }
}

Complexity

  • ⏰ Time complexity: O(m^2 * n), where m is the number of rows and n is the number of columns. We check all pairs of unique rows.
  • 🧺 Space complexity: O(m), for storing the bitmask to index mapping.