# Maximum Rows Covered by Columns
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-rows-covered-by-columns)
Canonical: https://scaleengineer.com/dsa/problems/maximum-rows-covered-by-columns
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Matrix
---
## 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 `1`s, 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.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-rows-covered-by-columns/image0.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:**

![](https://assets.glich.co/dsa/maximum-rows-covered-by-columns/image1.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`

# Approaches
## Brute-Force Backtracking
This approach directly translates the problem into a search algorithm. It uses recursion with backtracking to generate every possible combination of `numSelect` columns. For each generated combination, it performs a full scan of the matrix to count how many rows are covered. The maximum count found across all combinations is the final answer.
**Time:** O(C(n, numSelect) * m * n). The algorithm generates C(n, numSelect) combinations of columns. For each combination, it iterates through the entire `m x n` matrix to count covered rows. This is the slowest approach. · **Space:** O(numSelect). The space is used by the recursion stack, which goes up to a depth of `numSelect`, and the `HashSet` which stores up to `numSelect` column indices.
**Pros:** Conceptually simple and directly models the problem of choosing combinations.; Easy to implement without requiring advanced data structures or techniques.
**Cons:** Highly inefficient due to the expensive O(m * n) check being performed for every single combination.; The time complexity makes it too slow for larger constraints, although it passes for the given small constraints.
### Explanation
The main idea is to build a set of selected columns recursively. When the set reaches the desired size (`numSelect`), we evaluate it by checking every cell of the matrix. This is the most straightforward way to think about the problem but also the least performant.

```java
class Solution {
    int maxRows = 0;
    int m, n;
    int[][] matrix;

    public int maximumRows(int[][] matrix, int numSelect) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.matrix = matrix;
        
        generateCombinations(0, 0, new java.util.HashSet<>());
        return maxRows;
    }

    private void generateCombinations(int startCol, int count, java.util.Set<Integer> selectedCols) {
        if (count == numSelect) {
            int currentCoveredRows = 0;
            for (int i = 0; i < m; i++) {
                boolean rowCovered = true;
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 1 && !selectedCols.contains(j)) {
                        rowCovered = false;
                        break;
                    }
                }
                if (rowCovered) {
                    currentCoveredRows++;
                }
            }
            maxRows = Math.max(maxRows, currentCoveredRows);
            return;
        }

        for (int i = startCol; i < n; i++) {
            selectedCols.add(i);
            generateCombinations(i + 1, count + 1, selectedCols);
            selectedCols.remove(i); // Backtrack
        }
    }
}
```
### Algorithm
- Define a recursive helper function, say `generateCombinations(start_col, count, selected_cols)`.
- **Base Case:** When `count` equals `numSelect`, a valid combination `selected_cols` has been formed.
- For this combination, iterate through each row of the matrix.
- To check if a row is covered, verify that for every cell `matrix[i][j] == 1`, the column `j` is present in the `selected_cols` set.
- Count the number of covered rows for this combination and update a global maximum variable.
- **Recursive Step:** Iterate from `start_col` to `n-1`. For each column `i`:
    - Add column `i` to the current selection.
    - Make a recursive call: `generateCombinations(i + 1, count + 1, selected_cols)`.
    - Backtrack: Remove column `i` from the selection to explore other combinations.
- The initial call to start the process is `generateCombinations(0, 0, new HashSet<>())`.

## Bitmasking All Subsets
This approach leverages the small constraint on `n` (number of columns <= 12) by using bitmasks. A subset of columns can be represented by an integer, where the `j`-th bit is 1 if column `j` is selected. The algorithm iterates through all `2^n` possible column subsets. For each subset that has exactly `numSelect` columns (checked by counting set bits), it calculates the number of covered rows and updates the maximum.
**Time:** O(m * n + 2^n * m). The `m*n` is for preprocessing. The main loop runs `2^n` times, and inside it, we perform `m` checks. While `2^n` is larger than `C(n, numSelect)`, this approach is often faster than the first one because the work inside the loop is much smaller (O(m) vs O(m*n)). · **Space:** O(m). Space is required to store the `rowMasks` array.
**Pros:** Efficiently checks for covered rows using O(1) bitwise operations.; Avoids recursion overhead.; Faster than the naive backtracking approach because the `O(n)` factor in the inner loop is eliminated.
**Cons:** It checks all `2^n` subsets, even though we only care about subsets of size `numSelect`. This is less efficient than generating only the required combinations, especially when `numSelect` is much smaller than `n`.
### Explanation
The key improvement over the first approach is optimizing the row-checking process. We first pre-process the matrix to represent each row's requirements as a bitmask. This allows checking if a row is covered in a single O(1) bitwise operation, which is much faster than iterating through the row's columns.

```java
class Solution {
    public int maximumRows(int[][] matrix, int numSelect) {
        int m = matrix.length;
        int n = matrix[0].length;

        // Step 1: Pre-process matrix into row masks
        int[] rowMasks = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    rowMasks[i] |= (1 << j);
                }
            }
        }

        int maxCovered = 0;
        // Step 2: Iterate through all 2^n possible column selections (masks)
        for (int colMask = 0; colMask < (1 << n); colMask++) {
            // Step 3: Check if the mask has exactly numSelect columns
            if (Integer.bitCount(colMask) == numSelect) {
                int currentCovered = 0;
                // Step 4: Check how many rows are covered by this mask
                for (int rowMask : rowMasks) {
                    if ((rowMask & colMask) == rowMask) {
                        currentCovered++;
                    }
                }
                maxCovered = Math.max(maxCovered, currentCovered);
            }
        }
        return maxCovered;
    }
}
```
### Algorithm
- **Preprocessing:** Create an array `rowMasks` of size `m`. For each row `i`, `rowMasks[i]` is an integer where the `j`-th bit is set to 1 if `matrix[i][j] == 1`. This takes O(m * n) time.
- Initialize `maxCovered = 0`.
- Iterate through all possible column masks from `0` to `2^n - 1`. Let the current mask be `colMask`.
- Check if `colMask` represents a selection of exactly `numSelect` columns by checking if `Integer.bitCount(colMask) == numSelect`.
- If it is a valid selection, calculate the number of covered rows.
- Initialize `currentCovered = 0`. Iterate through each row `i` from `0` to `m-1`.
- A row `i` is covered if all its required columns (represented by `rowMasks[i]`) are included in the selected columns (`colMask`). This is checked efficiently with a bitwise AND: `(rowMasks[i] & colMask) == rowMasks[i]`.
- If the condition is true, increment `currentCovered`.
- After checking all rows, update the global maximum: `maxCovered = Math.max(maxCovered, currentCovered)`.
- Return `maxCovered`.

## Backtracking with Bitmask Optimization
This is the most optimal solution, combining the best aspects of the previous two approaches. It uses a backtracking algorithm to intelligently generate only the necessary combinations of `numSelect` columns, thus avoiding the `2^n` search space. Simultaneously, it uses bitmasks to represent both the column selections and row requirements, enabling a highly efficient O(1) check for whether a row is covered.
**Time:** O(m * n + C(n, numSelect) * m). O(m * n) for preprocessing. The recursion generates C(n, numSelect) valid masks, and for each, we do O(m) work. This is guaranteed to be faster than or equal to the other approaches. · **Space:** O(m + n). O(m) for `rowMasks` and O(n) (or more precisely, O(numSelect)) for the recursion stack depth.
**Pros:** Most efficient solution with the best time complexity.; Combines the targeted search of backtracking with the fast checking of bitmasking.; Avoids iterating through unnecessary combinations.
**Cons:** Slightly more complex to conceptualize and implement, as it requires understanding both backtracking and bit manipulation.
### Explanation
We generate combinations using recursion, but instead of passing a `Set` of columns, we build up a bitmask representing the selection. This allows us to use the efficient row-checking method from the second approach while only visiting the C(n, numSelect) combinations that are relevant, giving us the best of both worlds.

```java
class Solution {
    int maxRows = 0;
    int m, n;
    int[] rowMasks;

    public int maximumRows(int[][] matrix, int numSelect) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        
        // Step 1: Pre-process matrix into row masks
        this.rowMasks = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    rowMasks[i] |= (1 << j);
                }
            }
        }
        
        generateCombinations(0, numSelect, 0);
        return maxRows;
    }

    private void generateCombinations(int startCol, int k, int currentMask) {
        // Base case: a combination of k columns is formed
        if (k == 0) {
            int currentCoveredRows = 0;
            for (int rowMask : rowMasks) {
                if ((rowMask & currentMask) == rowMask) {
                    currentCoveredRows++;
                }
            }
            maxRows = Math.max(maxRows, currentCoveredRows);
            return;
        }

        // Pruning: if remaining columns are not enough to select k
        if (n - startCol < k) {
            return;
        }

        // Recursive step: iterate through possible next columns
        for (int i = startCol; i < n; i++) {
            // Select column i and recurse
            generateCombinations(i + 1, k - 1, currentMask | (1 << i));
        }
    }
}
```
### Algorithm
- **Preprocessing:** Same as the previous approach, create the `rowMasks` array in O(m * n) time.
- Create a recursive function `generate(start_col, k, current_mask)`, where `k` is the number of columns left to choose.
- **Base Case:** If `k` is 0, we have a valid combination in `current_mask`.
    - Count covered rows by iterating through `rowMasks` and checking if `(rowMask & current_mask) == rowMask`. This takes O(m) time.
    - Update the global maximum.
- **Recursive Step:** For each column `i` from `start_col` to `n-1`:
    - Recurse, selecting column `i`: `generate(i + 1, k - 1, current_mask | (1 << i))`.

# Solutions
### Java

```java
class Solution {
public
  int maximumRows(int[][] matrix, int numSelect) {
    int m = matrix.length, n = matrix[0].length;
    int[] rows = new int[m];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j] == 1) {
          rows[i] |= 1 << j;
        }
      }
    }
    int ans = 0;
    for (int mask = 1; mask < 1 << n; ++mask) {
      if (Integer.bitCount(mask) != numSelect) {
        continue;
      }
      int t = 0;
      for (int x : rows) {
        if ((x & mask) == x) {
          ++t;
        }
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumRows(vector<vector<int>> &matrix, int numSelect) {
    int m = matrix.size(), n = matrix[0].size();
    int rows[m];
    memset(rows, 0, sizeof(rows));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j]) {
          rows[i] |= 1 << j;
        }
      }
    }
    int ans = 0;
    for (int mask = 1; mask < 1 << n; ++mask) {
      if (__builtin_popcount(mask) != numSelect) {
        continue;
      }
      int t = 0;
      for (int x : rows) {
        t += (x & mask) == x;
      }
      ans = max(ans, t);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int: rows = [] for row in matrix: mask = reduce(or_, (1 << j for j, x in enumerate(row) if x), 0) rows . append(mask) ans = 0 for mask in range(1 << len(matrix[0])): if mask . bit_count() != numSelect: continue t = sum((x & mask) == x for x in rows) ans = max(ans, t) return ans

```