Find a good subset of the matrix

Array Hash Table Bit Manipulation Matrix

46.7% acceptance

Feb 25, 2026

213

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn good_subsetof_binary_matrix(grid: Vec<Vec<i32>>) -> Vec<i32> {
    let n_cols = grid[0].len();
    let full = (1u8 << n_cols) - 1;

    // Map mask -> first row index
    let mut mask_to_row: std::collections::HashMap<u8, i32> = std::collections::HashMap::new();

    for (i, row) in grid.iter().enumerate() {
      let mut mask = 0u8;
      for &v in row { mask = (mask << 1) | v as u8; }

      if mask == 0 {
        return vec![i as i32];
      }

      // Check if any existing mask is disjoint with this one
      // Enumerate submasks of complement
      let comp = (!mask) & full;
      let mut sub = comp;
      loop {
        if let Some(&j) = mask_to_row.get(&sub) {
          let mut res = vec![j, i as i32];
          res.sort();
          return res;
        }
        if sub == 0 { break; }
        sub = (sub - 1) & comp;
      }

      mask_to_row.entry(mask).or_insert(i as i32);
    }
    vec![]
  }
}