Skip to content

2397. Maximum Rows Covered by Columns 👎

  • Time: $O(mn \cdot 2^n)$
  • Space: $O(2^n)$
 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
28
29
30
31
32
33
34
35
36
37
38
39
40
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;
  }
};

 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
28
29
30
31
32
33
34
35
36
37
38
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;
  }
}

 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
28
29
30
31
32
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, cell in enumerate(row):
        if cell == 1 and (mask >> i & 1) == 0:
          isAllZeros = False
          break
      if isAllZeros:
        count += 1
    return count