Problem

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.

Examples

Example 1

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


![](https://assets.leetcode.com/uploads/2022/07/14/rowscovered.png)

Input: matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2

Output: 3

Explanation:

One possible way to cover 3 rows is shown in the diagram above.  
We choose s = {0, 2}.  
\- Row 0 is covered because it has no occurrences of 1.  
\- Row 1 is covered because the columns with value 1, i.e. 0 and 2 are present
in s.  
\- Row 2 is not covered because matrix[2][1] == 1 but 1 is not present in s.  
\- Row 3 is covered because matrix[2][2] == 1 and 2 is present in s.  
Thus, we can cover three rows.  
Note that s = {1, 2} will also cover 3 rows, but it can be shown that no more
than three rows can be covered.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


![](https://assets.leetcode.com/uploads/2022/07/14/rowscovered2.png)

Input: matrix = [[1],[0]], numSelect = 1

Output: 2

Explanation:

Selecting the only column will result in both rows being covered since the
entire matrix is selected.

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 12
  • matrix[i][j] is either 0 or 1.
  • 1 <= numSelect <= n

Solution

Method 1 – Bitmask Enumeration

Intuition

Since the number of columns is small (≤12), we can try all possible combinations of columns to select. For each combination, we check how many rows are covered. Using bitmasks makes it efficient to represent both the selected columns and the required columns for each row.

Approach

  1. For each row, create a bitmask representing which columns must be selected to cover that row (i.e., where the row has 1s).
  2. Enumerate all possible combinations of numSelect columns using bitmasks.
  3. For each combination, count how many rows are covered (i.e., the row’s bitmask is a subset of the selected columns’ bitmask).
  4. Track and return the maximum number of covered rows.

Code

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

class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int m = matrix.size(), n = matrix[0].size(), ans = 0;
        vector<int> rowMask(m, 0);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (matrix[i][j]) rowMask[i] |= (1 << j);
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (__builtin_popcount(mask) != numSelect) continue;
            int cnt = 0;
            for (int r : rowMask)
                if ((r & mask) == r) cnt++;
            ans = max(ans, cnt);
        }
        return ans;
    }
};
 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
26
27

func maximumRows(matrix [][]int, numSelect int) int {
    m, n := len(matrix), len(matrix[0])
    rowMask := make([]int, m)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == 1 {
                rowMask[i] |= 1 << j
            }
        }
    }
    ans := 0
    for mask := 0; mask < (1 << n); mask++ {
        if bits.OnesCount(uint(mask)) != numSelect {
            continue
        }
        cnt := 0
        for _, r := range rowMask {
            if r&mask == r {
                cnt++
            }
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maximumRows(int[][] matrix, int numSelect) {
        int m = matrix.length, n = matrix[0].length, ans = 0;
        int[] rowMask = new int[m];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (matrix[i][j] == 1) rowMask[i] |= (1 << j);
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (Integer.bitCount(mask) != numSelect) continue;
            int cnt = 0;
            for (int r : rowMask)
                if ((r & mask) == r) cnt++;
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maximumRows(matrix: Array<IntArray>, numSelect: Int): Int {
        val m = matrix.size
        val n = matrix[0].size
        val rowMask = IntArray(m)
        for (i in 0 until m)
            for (j in 0 until n)
                if (matrix[i][j] == 1) rowMask[i] = rowMask[i] or (1 shl j)
        var ans = 0
        for (mask in 0 until (1 shl n)) {
            if (mask.countOneBits() != numSelect) continue
            var cnt = 0
            for (r in rowMask)
                if ((r and mask) == r) cnt++
            ans = maxOf(ans, cnt)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maximumRows(self, matrix: list[list[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        row_mask = [sum(val << j for j, val in enumerate(row)) for row in matrix]
        ans = 0
        for mask in range(1 << n):
            if bin(mask).count('1') != numSelect:
                continue
            cnt = sum((r & mask) == r for r in row_mask)
            ans = max(ans, cnt)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn maximum_rows(matrix: Vec<Vec<i32>>, num_select: i32) -> i32 {
        let m = matrix.len();
        let n = matrix[0].len();
        let mut row_mask = vec![0; m];
        for i in 0..m {
            for j in 0..n {
                if matrix[i][j] == 1 {
                    row_mask[i] |= 1 << j;
                }
            }
        }
        let mut ans = 0;
        for mask in 0..(1 << n) {
            if mask.count_ones() != num_select as u32 { continue; }
            let mut cnt = 0;
            for &r in &row_mask {
                if (r & mask) == r { cnt += 1; }
            }
            ans = ans.max(cnt);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maximumRows(matrix: number[][], numSelect: number): number {
        const m = matrix.length, n = matrix[0].length;
        const rowMask = matrix.map(row => row.reduce((acc, val, j) => acc | (val << j), 0));
        let ans = 0;
        for (let mask = 0; mask < (1 << n); mask++) {
            if (mask.toString(2).split('1').length - 1 !== numSelect) continue;
            let cnt = 0;
            for (const r of rowMask)
                if ((r & mask) === r) cnt++;
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * 2^n), since we enumerate all subsets of columns (up to 2^n) and for each, check all m rows.
  • 🧺 Space complexity: O(m), for storing the bitmask of each row.