Skip to content

861. Score After Flipping Matrix 👍

Approach 1: Naive Greedy

  • Time: $O(mn)$
  • Space: $O(mn)$
 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
41
42
43
44
45
46
47
48
49
class Solution {
 public:
  int matrixScore(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = 0;

    // Flip rows with leading 0
    for (auto& row : grid)
      if (row[0] == 0)
        flip(row);

    // Flip cols with 1s < 0s
    for (int j = 0; j < n; ++j)
      if (onesColCount(grid, j) * 2 < m)
        flipCol(grid, j);

    // Add binary number for each row
    for (const vector<int>& row : grid)
      ans += binary(row);

    return ans;
  }

 private:
  void flip(vector<int>& row) {
    for (int i = 0; i < row.size(); ++i)
      row[i] ^= 1;
  }

  int onesColCount(const vector<vector<int>>& grid, int j) {
    int ones = 0;
    for (int i = 0; i < grid.size(); ++i)
      ones += grid[i][j];
    return ones;
  }

  void flipCol(vector<vector<int>>& grid, int j) {
    for (int i = 0; i < grid.size(); ++i)
      grid[i][j] ^= 1;
  }

  int binary(const vector<int>& row) {
    int res = row[0];
    for (int j = 1; j < row.size(); ++j)
      res = res * 2 + row[j];
    return res;
  }
};

 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
41
42
43
44
45
46
47
class Solution {
  public int matrixScore(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = 0;

    // Flip rows with leading 0
    for (int[] row : grid)
      if (row[0] == 0)
        flip(row);

    // Flip cols with 1s < 0s
    for (int j = 0; j < n; ++j)
      if (onesColCount(grid, j) * 2 < m)
        flipCol(grid, j);

    // Add binary number for each row
    for (int[] row : grid)
      ans += binary(row);

    return ans;
  }

  private void flip(int[] row) {
    for (int i = 0; i < row.length; ++i)
      row[i] ^= 1;
  }

  private int onesColCount(int[][] grid, int j) {
    int ones = 0;
    for (int i = 0; i < grid.length; ++i)
      ones += grid[i][j];
    return ones;
  }

  private void flipCol(int[][] grid, int j) {
    for (int i = 0; i < grid.length; ++i)
      grid[i][j] ^= 1;
  }

  private int binary(int[] row) {
    int res = row[0];
    for (int j = 1; j < row.length; ++j)
      res = res * 2 + row[j];
    return res;
  }
}

 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
class Solution:
  def matrixScore(self, grid: List[List[int]]) -> int:
    # Flip rows with leading 0
    for row in grid:
      if row[0] == 0:
        self._flip(row)

    # Flip cols with 1s < 0s
    for j, col in enumerate(list(zip(*grid))):
      if sum(col) * 2 < len(grid):
        self._flipCol(grid, j)

    # Add binary number for each row
    return sum(self._binary(row) for row in grid)

  def _flip(self, row: List[int]) -> None:
    for i in range(len(row)):
      row[i] ^= 1

  def _flipCol(self, grid: List[List[int]], j: int) -> None:
    for i in range(len(grid)):
      grid[i][j] ^= 1

  def _binary(self, row: List[int]) -> int:
    res = row[0]
    for j in range(1, len(row)):
      res = res * 2 + row[j]
    return res

Approach 2: Heuristic

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int matrixScore(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = m;  // All cells in the first col are 1

    for (int j = 1; j < n; ++j) {
      int onesCount = 0;
      for (int i = 0; i < m; ++i)
        // The best strategy is flip a row with leading 0
        onesCount += grid[i][j] == grid[i][0];
      ans = ans * 2 + max(onesCount, m - onesCount);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int matrixScore(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = m; // All cells in the first col are 1

    for (int j = 1; j < n; ++j) {
      int onesCount = 0;
      for (int i = 0; i < m; ++i)
        // The best strategy is flip a row with leading 0
        onesCount += grid[i][j] == grid[i][0] ? 1 : 0;
      ans = ans * 2 + Math.max(onesCount, m - onesCount);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def matrixScore(self, grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    ans = m  # All cells in the first col are 1

    for j in range(1, n):
      # The best strategy is flip a row with leading 0
      onesCount = sum(grid[i][j] == grid[i][0] for i in range(m))
      ans = ans * 2 + max(onesCount, m - onesCount)

    return ans