Skip to content

3240. Minimum Number of Flips to Make Binary Grid Palindromic II

  • Time: $O(mn)$
  • Space: $O(1)$
 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
50
51
class Solution {
 public:
  int minFlips(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = 0;
    int middleOnes = 0;
    int mismatchedPairs = 0;

    // Handle top-left, top-right, bottom-left, bottom-right cells.
    for (int i = 0; i < m / 2; ++i)
      for (int j = 0; j < n / 2; ++j) {
        const int ones = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] +
                         grid[m - 1 - i][n - 1 - j];
        ans += min(ones, 4 - ones);
      }

    // Handle the middle row if the number of m is odd.
    if (m % 2 == 1)
      for (int j = 0; j < n / 2; ++j) {
        const int leftCell = grid[m / 2][j];
        const int rightCell = grid[m / 2][n - 1 - j];
        mismatchedPairs += leftCell ^ rightCell;
        middleOnes += leftCell + rightCell;
      }

    // Handle the middle column if the number of columns is odd.
    if (n % 2 == 1)
      for (int i = 0; i < m / 2; ++i) {
        const int topCell = grid[i][n / 2];
        const int bottomCell = grid[m - 1 - i][n / 2];
        mismatchedPairs += topCell ^ bottomCell;
        middleOnes += topCell + bottomCell;
      }

    if (mismatchedPairs == 0) {
      // Since there's no mismatched pairs, middleOnes % 4 must be 0 or 2.
      if (middleOnes % 4 == 2)
        ans += 2;  // Flip two 1s to 0s.
    } else {
      // Flip every mismatched pair 01 to 00 or 11. It doesn't matter.
      ans += mismatchedPairs;
    }

    // Handle the center cell if both dimensions are odd.
    if (m % 2 == 1 && n % 2 == 1)
      ans += grid[m / 2][n / 2];

    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
  public int minFlips(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = 0;
    int middleOnes = 0;
    int mismatchedPairs = 0;

    // Handle top-left, top-right, bottom-left, bottom-right cells.
    for (int i = 0; i < m / 2; ++i) {
      for (int j = 0; j < n / 2; ++j) {
        final int ones =
            grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j];
        ans += Math.min(ones, 4 - ones);
      }
    }

    // Handle the middle row if the number of m is odd.
    if (m % 2 == 1)
      for (int j = 0; j < n / 2; ++j) {
        final int leftCell = grid[m / 2][j];
        final int rightCell = grid[m / 2][n - 1 - j];
        mismatchedPairs += leftCell ^ rightCell;
        middleOnes += leftCell + rightCell;
      }

    // Handle the middle column if the number of columns is odd.
    if (n % 2 == 1)
      for (int i = 0; i < m / 2; ++i) {
        final int topCell = grid[i][n / 2];
        final int bottomCell = grid[m - 1 - i][n / 2];
        mismatchedPairs += topCell ^ bottomCell;
        middleOnes += topCell + bottomCell;
      }

    if (mismatchedPairs == 0) {
      // Since there's no mismatched pairs, middleOnes % 4 must be 0 or 2.
      if (middleOnes % 4 == 2)
        ans += 2; // Flip two 1s to 0s.
    } else {
      // Flip every mismatched pair 01 to 00 or 11. It doesn't matter.
      ans += mismatchedPairs;
    }

    // Handle the center cell if both dimensions are odd.
    if (m % 2 == 1 && n % 2 == 1)
      ans += grid[m / 2][n / 2];

    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
  def minFlips(self, grid: list[list[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    ans = 0
    middleOnes = 0
    mismatchedPairs = 0

    # Handle top-left, top-right, bottom-left, bottom-right cells.
    for i in range(m // 2):
      for j in range(n // 2):
        ones = (grid[i][j] + grid[i][n - 1 - j] +
                grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j])
        ans += min(ones, 4 - ones)

    # Handle the middle row if the number of m is odd.
    if m % 2 == 1:
      for j in range(n // 2):
        leftCell = grid[m // 2][j]
        rightCell = grid[m // 2][n - 1 - j]
        mismatchedPairs += leftCell ^ rightCell
        middleOnes += leftCell + rightCell

    # Handle the middle column if the number of columns is odd.
    if n % 2 == 1:
      for i in range(m // 2):
        topCell = grid[i][n // 2]
        bottomCell = grid[m - 1 - i][n // 2]
        mismatchedPairs += topCell ^ bottomCell
        middleOnes += topCell + bottomCell

    if mismatchedPairs == 0:
      # Since there's no mismatched pairs, middleOnes % 4 must be 0 or 2.
      if middleOnes % 4 == 2:
        ans += 2  # Flip two 1s to 0s.
    else:
      # Flip every mismatched pair 01 to 00 or 11. It doesn't matter.
      ans += mismatchedPairs

    # Handle the center cell if both dimensions are odd.
    if m % 2 == 1 and n % 2 == 1:
      ans += grid[m // 2][n // 2]

    return ans