Scale Engineer

Minimum Number of Flips to Make Binary Grid Palindromic II

Med
#2877Time: O(G * S), where G is the number of symmetric groups (at most m*n) and S is the maximum number of ones (m*n). This leads to a complexity of O((m*n)^2).Space: O(m*n) to store the DP table. The number of groups is also proportional to m*n, but they can be processed on the fly.
Patterns
Two Pointers
Data structures
ArrayMatrix

Prompt

You are given an m x n binary matrix grid.

A row or column is considered palindromic if its values read the same forward and backward.

You can flip any number of cells in grid from 0 to 1, or from 1 to 0.

Return the minimum number of cells that need to be flipped to make all rows and columns palindromic, and the total number of 1's in grid divisible by 4.

 

Example 1:

Input: grid = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

Explanation:

Example 2:

Input: grid = [[0,1],[0,1],[0,0]]

Output: 2

Explanation:

Example 3:

Input: grid = [[1],[1]]

Output: 2

Explanation:

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m * n <= 2 * 105
  • 0 <= grid[i][j] <= 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem by keeping track of the exact number of ones accumulated. While it correctly models the problem, its state space is very large, making it inefficient for the given constraints.

Algorithm

  • Symmetric Group Decomposition:
    1. The first step is to realize that for the grid to be palindromic across all rows and columns, certain cells must have the same value. These cells form symmetric groups.
    2. For any cell (i, j), the cells (i, n-1-j), (m-1-i, j), and (m-1-i, n-1-j) must all have the same value. These four cells form a symmetric group of size 4.
    3. If a row or column is in the middle (i.e., m or n is odd), the groups might be of size 2 or 1.
    4. Iterate through the top-left quadrant of the grid to identify all unique symmetric groups and their original values.
  • Cost Calculation:
    1. For each group, calculate the cost to make all its cells 0 (cost0, which is the number of 1s in the group) and the cost to make all its cells 1 (cost1, which is the number of 0s in the group).
  • Dynamic Programming:
    1. Define a DP state dp[i][j] representing the minimum number of flips required using the first i groups to achieve a total of exactly j ones in the final grid.
    2. The DP table size will be (number of groups + 1) x (m*n + 1).
    3. Initialize dp[0][0] = 0 and all other entries to infinity.
    4. The transition for group i (with size k_i, costs cost0_i, cost1_i) is: dp[i][j] = min(dp[i-1][j] + cost0_i, dp[i-1][j - k_i] + cost1_i)
    5. This can be space-optimized to use a 1D DP array dp[j] of size m*n + 1.
  • Final Result:
    1. After iterating through all groups, the DP table dp[j] will hold the minimum flips to get j ones.
    2. The final answer is the minimum value among dp[j] for all j that are divisible by 4.

Walkthrough

The core idea is to break down the problem into smaller, independent subproblems. The palindromic constraints force certain cells to be equal. We can group these cells together. For each group, we have two choices: make all cells 0 or make all cells 1. This problem can be framed as a variation of the knapsack problem.

We define a DP state dp[j] as the minimum flips to achieve exactly j ones. We iterate through each symmetric group and update the DP table based on the two choices for that group.

For a group of size k with costs cost0 and cost1:

  • To make it all 0s, we add cost0 flips and 0 ones.
  • To make it all 1s, we add cost1 flips and k ones.

We build up the dp table group by group. After considering all groups, we look for the minimum flips among all states dp[j] where j is a multiple of 4.

// This is a conceptual implementation and will likely time out.class Solution {    public int minFlips(int[][] grid) {        int m = grid.length;        int n = grid[0].length;        List<int[]> groups = new ArrayList<>();        boolean[][] visited = new boolean[m][n];         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (visited[i][j]) continue;                 List<int[]> cells = new ArrayList<>();                cells.add(new int[]{i, j});                visited[i][j] = true;                 int r1 = i, c1 = n - 1 - j;                if (!visited[r1][c1]) { cells.add(new int[]{r1, c1}); visited[r1][c1] = true; }                int r2 = m - 1 - i, c2 = j;                if (!visited[r2][c2]) { cells.add(new int[]{r2, c2}); visited[r2][c2] = true; }                int r3 = m - 1 - i, c3 = n - 1 - j;                if (!visited[r3][c3]) { cells.add(new int[]{r3, c3}); visited[r3][c3] = true; }                 int ones = 0;                for (int[] cell : cells) {                    if (grid[cell[0]][cell[1]] == 1) {                        ones++;                    }                }                int size = cells.size();                int zeros = size - ones;                groups.add(new int[]{size, ones, zeros}); // {k, cost0, cost1}            }        }         int[] dp = new int[m * n + 1];        Arrays.fill(dp, Integer.MAX_VALUE);        dp[0] = 0;         for (int[] group : groups) {            int k = group[0];            int cost0 = group[1];            int cost1 = group[2];            int[] newDp = new int[m * n + 1];            Arrays.fill(newDp, Integer.MAX_VALUE);             for (int j = 0; j <= m * n; j++) {                if (dp[j] != Integer.MAX_VALUE) {                    // Option 1: Make group all 0s                    newDp[j] = Math.min(newDp[j], dp[j] + cost0);                    // Option 2: Make group all 1s                    if (j + k <= m * n) {                        newDp[j + k] = Math.min(newDp[j + k], dp[j] + cost1);                    }                }            }            dp = newDp;        }         int minFlips = Integer.MAX_VALUE;        for (int j = 0; j <= m * n; j += 4) {            minFlips = Math.min(minFlips, dp[j]);        }         return minFlips;    }}

Complexity

Time

O(G * S), where G is the number of symmetric groups (at most m*n) and S is the maximum number of ones (m*n). This leads to a complexity of O((m*n)^2).

Space

O(m*n) to store the DP table. The number of groups is also proportional to m*n, but they can be processed on the fly.

Trade-offs

Pros

  • It is a direct and conceptually straightforward application of dynamic programming.

  • It correctly solves the problem for smaller grid sizes.

Cons

  • The time complexity of O((m*n)^2) is too high for the given constraints and will result in a Time Limit Exceeded error.

  • The space complexity of O(m*n) can be very large, potentially causing memory issues for the largest grids.

Solutions

class Solution {public  int minFlips(int[][] grid) {    int m = grid.length, n = grid[0].length;    int ans = 0;    for (int i = 0; i < m / 2; ++i) {      for (int j = 0; j < n / 2; ++j) {        int x = m - i - 1, y = n - j - 1;        int cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y];        ans += Math.min(cnt1, 4 - cnt1);      }    }    if (m % 2 == 1 && n % 2 == 1) {      ans += grid[m / 2][n / 2];    }    int diff = 0, cnt1 = 0;    if (m % 2 == 1) {      for (int j = 0; j < n / 2; ++j) {        if (grid[m / 2][j] == grid[m / 2][n - j - 1]) {          cnt1 += grid[m / 2][j] * 2;        } else {          diff += 1;        }      }    }    if (n % 2 == 1) {      for (int i = 0; i < m / 2; ++i) {        if (grid[i][n / 2] == grid[m - i - 1][n / 2]) {          cnt1 += grid[i][n / 2] * 2;        } else {          diff += 1;        }      }    }    ans += cnt1 % 4 == 0 || diff > 0 ? diff : 2;    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem