2397. Maximum Rows Covered by Columns LeetCode Solution

In this guide, you will get 2397. Maximum Rows Covered by Columns LeetCode Solution with the best time and space complexity. The solution to Maximum Rows Covered by Columns problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Rows Covered by Columns solution in C++
4. Maximum Rows Covered by Columns solution in Java
5. Maximum Rows Covered by Columns solution in Python
6. Additional Resources

Problem Statement of Maximum Rows Covered by Columns

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.

Example 1:

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:

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

Complexity Analysis

• Time Complexity: O(mn \cdot 2^n)
• Space Complexity: O(2^n)

2397. Maximum Rows Covered by Columns LeetCode Solution in C++

class Solution {
 public:
  int maximumRows(vector<vector<int>>& matrix, int numSelect) {
    int ans = 0;
    dfs(matrix, /*colIndex=*/0, numSelect, /*mask=*/0, ans);
    return ans;
  }

 private:
  void dfs(const vector<vector<int>>& matrix, int colIndex, int leftColsCount,
           int mask, int& ans) {
    if (leftColsCount == 0) {
      ans = max(ans, getAllZerosRowCount(matrix, mask));
      return;
    }
    if (colIndex == matrix[0].size())
      return;

    // Choose this column.
    dfs(matrix, colIndex + 1, leftColsCount - 1, mask | 1 << colIndex, ans);
    // Don't choose this column.
    dfs(matrix, colIndex + 1, leftColsCount, mask, ans);
  }

  int getAllZerosRowCount(const vector<vector<int>>& matrix, int mask) {
    int count = 0;
    for (const vector<int>& row : matrix) {
      bool isAllZeros = true;
      for (int i = 0; i < row.size(); ++i) {
        if (row[i] == 1 && (mask >> i & 1) == 0) {
          isAllZeros = false;
          break;
        }
      }
      if (isAllZeros)
        ++count;
    }
    return count;
  }
};
/* code provided by PROGIEZ */

2397. Maximum Rows Covered by Columns LeetCode Solution in Java

class Solution {
  public int maximumRows(int[][] matrix, int numSelect) {
    dfs(matrix, /*colIndex=*/0, numSelect, /*mask=*/0);
    return ans;
  }

  private int ans = 0;

  private void dfs(int[][] matrix, int colIndex, int leftColsCount, int mask) {
    if (leftColsCount == 0) {
      ans = Math.max(ans, getAllZerosRowCount(matrix, mask));
      return;
    }
    if (colIndex == matrix[0].length)
      return;

    // Choose this column.
    dfs(matrix, colIndex + 1, leftColsCount - 1, mask | 1 << colIndex);
    // Don't choose this column.
    dfs(matrix, colIndex + 1, leftColsCount, mask);
  }

  int getAllZerosRowCount(int[][] matrix, int mask) {
    int count = 0;
    for (int[] row : matrix) {
      boolean isAllZeros = true;
      for (int i = 0; i < row.length; ++i) {
        if (row[i] == 1 && (mask >> i & 1) == 0) {
          isAllZeros = false;
          break;
        }
      }
      if (isAllZeros)
        ++count;
    }
    return count;
  }
}
// code provided by PROGIEZ

2397. Maximum Rows Covered by Columns LeetCode Solution in Python

class Solution:
  def maximumRows(self, matrix: list[list[int]], numSelect: int) -> int:
    ans = 0

    def dfs(colIndex: int, leftColsCount: int, mask: int):
      nonlocal ans
      if leftColsCount == 0:
        ans = max(ans, self._getAllZerosRowCount(matrix, mask))
        return

      if colIndex == len(matrix[0]):
        return

      # Choose this column.
      dfs(colIndex + 1, leftColsCount - 1, mask | 1 << colIndex)
      # Don't choose this column.
      dfs(colIndex + 1, leftColsCount, mask)

    dfs(0, numSelect, 0)
    return ans

  def _getAllZerosRowCount(self, matrix: list[list[int]], mask: int) -> int:
    count = 0
    for row in matrix:
      isAllZeros = True
      for i, num in enumerate(row):
        if num == 1 and (mask >> i & 1) == 0:
          isAllZeros = False
          break
      if isAllZeros:
        count += 1
    return count
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.