Maximum rows covered by columns

Array Backtracking Bit Manipulation Matrix Enumeration

57.7% acceptance

Feb 25, 2026

294

442

You are given an m x n binary matrix matrix and an integer numSelect. Your goal is to select exactly numSelect distinct columns from matrix such that you cover as many rows as possible. A row is considered covered if all the 1's in that row are also part of a column that you have selected. If a row does not have any 1s, it is also considered covered. More formally, let us consider selected = {c1, c2, ...., cnumSelect} as the set of columns selected by you. A row i is covered by selected if: For each cell where matrix[i][j] == 1, the column j is in selected. Or, no cell in row i has a value of 1. Return the maximum number of rows that can be covered by a set of numSelect columns.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_rows(matrix: Vec<Vec<i32>>, num_select: i32) -> i32 {
    let cols = matrix[0].len();
    let row_masks: Vec<u32> = matrix.iter().map(|row| {
      row.iter().enumerate().fold(0u32, |acc, (j, &v)| acc | ((v as u32) << j))
    }).collect();
    let mut best = 0;
    for mask in 0u32..(1 << cols) {
      if mask.count_ones() == num_select as u32 {
        let covered = row_masks.iter().filter(|&&r| r & mask == r).count();
        best = best.max(covered);
      }
    }
    best as i32
  }
}