Skip to main content
Talentd

Minimum Number of Flips to Make Binary Grid Palindromic I - Solution & Explanation

MediumArrayTwo PointersMatrix10 min read
Practice this problem

Problem Statement

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 either all rows palindromic or all columns palindromic.

 

Example 1:

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

Output: 2

Explanation:

Flipping the highlighted cells makes all the rows palindromic.

Example 2:

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

Output: 1

Explanation:

Flipping the highlighted cell makes all the columns palindromic.

Example 3:

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

Output: 0

Explanation:

All rows are already palindromic.

 

Constraints:

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

Approach Overview

Problem Overview: You are given a binary matrix. A row or column is palindromic if reading it from left-to-right equals right-to-left. The task is to compute the minimum number of cell flips needed so that either every row becomes palindromic or every column becomes palindromic.

Approach 1: Greedy Row/Column Two-Pointer Scan (O(m*n) time, O(1) space)

The grid can be fixed in two independent ways: make all rows palindromic or make all columns palindromic. For rows, iterate each row and use the classic two pointers technique. Start one pointer at the left and one at the right. If grid[r][l] and grid[r][r] differ, one flip is required to make the pair equal. Count mismatches for every symmetric pair and sum them across rows. The same idea applies to columns: scan each column with pointers from top and bottom and count mismatched pairs.

The key observation: every symmetric pair must contain identical values for the row or column to be palindromic. Flipping either cell resolves the mismatch, so each mismatch contributes exactly one flip. Compute the total flips needed for rows and the total for columns, then return the smaller value. This greedy counting works because each pair is independent and there is no cross-pair dependency.

This method uses only simple iteration over the array structure representing the grid. No extra memory or preprocessing is required, which keeps the implementation short and efficient.

Approach 2: Dynamic Programming Pair Aggregation (O(m*n) time, O(1) space)

A DP-style interpretation treats every symmetric pair as a small subproblem. For a row, the pair (i, j) and (i, n-1-j) must end with the same value. The minimum flips for the pair is 0 if the values already match and 1 otherwise. A DP transition simply accumulates the optimal cost for each processed pair. Repeating this across all rows produces the total row cost; repeating across columns produces the column cost.

Although labeled as dynamic programming, the state transition collapses to a direct mismatch count because each pair decision is independent. The DP framing can still help when reasoning about extensions of the problem (for example when flips have different costs or when multiple constraints interact).

Recommended for interviews: The greedy two-pointer approach is the expected solution. It demonstrates clear reasoning about symmetry and efficient traversal of a matrix. A brute-force mindset would attempt flipping cells and rechecking palindromes, but recognizing that only symmetric pairs matter reduces the problem to a linear scan. Interviewers typically look for this observation and an O(m*n) implementation.

Approach 1: Greedy Approach for Rows or Columns

This approach focuses on checking each row and each column to calculate the number of flips required to make them palindromic.

For rows, iterate through half of the row. For each element, compare it with its corresponding element from the opposite end. If they differ, increment the flip counter.

Repeat the process for each column and compute the minimum flips needed for each column. Finally, return the minimum flips between making all rows palindromic and all columns palindromic.

Here, we define a helper function flips_for_palindrome to calculate the minimum number of flips required to make an array palindromic.

We calculate the flip counts for all rows and all columns using this helper and return the minimum between the two.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(m * n), where m and n are the dimensions of the grid. This is because we iterate through each element once to calculate flips for rows and columns.

Space Complexity: O(1), as we use constant extra space for counting flips.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

Utilizing dynamic programming (DP) techniques, we can compute minimum flips needed to make binary sequences palindromic once and store the results to reuse for each row and column.

This involves first pre-calculating the cost of flips for sequences of possible lengths which speeds up the process of determining minimum flips for rows and columns.

In Java, similar logic is applied. We determine necessary flips for all rows and columns using two arrays: rowFlips and colFlips.

Each position's flips are calculated once and stored for efficient retrieval during comparisons.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(m * n), as each cell is processed once to compute the flip values.

Space Complexity: O(m + n), used by the arrays storing flips for rows and columns.

Try this approach in the editor →

Approach 3: Counting

We separately count the number of flips for rows and columns, denoted as cnt1 and cnt2, respectively. Finally, we take the minimum of the two.

The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix grid, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach for Rows or Columns

Time Complexity: O(m * n), where m and n are the dimensions of the grid. This is because we iterate through each element once to calculate flips for rows and columns.

Space Complexity: O(1), as we use constant extra space for counting flips.

Dynamic Programming Approach

Time Complexity: O(m * n), as each cell is processed once to compute the flip values.

Space Complexity: O(m + n), used by the arrays storing flips for rows and columns.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Two-Pointer Scan (Rows vs Columns)O(m*n)O(1)Best general solution. Directly counts mismatched symmetric pairs in rows and columns.
Dynamic Programming Pair AggregationO(m*n)O(1)Useful for reasoning about symmetric pair costs or when extending the problem with additional constraints.

Video Solution

Minimum Number of Flips to Make Binary Grid Palindromic I | Biweekly Contest 136 | Leetcode Solution • codi • 1,252 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Minimum Number of Flips to Make Binary Grid Palindromic I easy or hard?
The problem is rated Medium on LeetCode. The implementation is straightforward once you recognize that only symmetric pairs affect palindrome validity. The main challenge is identifying that you should evaluate rows and columns separately and choose the minimum cost.
Minimum Number of Flips to Make Binary Grid Palindromic I Python/Java solution
A typical Python or Java solution iterates through rows and columns, compares symmetric indices, and counts mismatches. Python implementations often use simple loops, while Java solutions may structure the logic in helper methods. Both achieve O(m*n) time and constant extra space.
How to solve Minimum Number of Flips to Make Binary Grid Palindromic I in O(m*n)?
Traverse each row with two pointers from both ends and count mismatched pairs. Do the same for each column by comparing top and bottom cells. Each mismatch requires one flip. Return the smaller total between the row-based flips and column-based flips.
What is the best approach for Minimum Number of Flips to Make Binary Grid Palindromic I?
The most efficient approach scans symmetric pairs using a two-pointer technique. Count mismatches in every row to compute the cost of making rows palindromic, then repeat for columns. The answer is the minimum of the two totals. This runs in O(m*n) time with O(1) extra space.
Is Minimum Number of Flips to Make Binary Grid Palindromic I asked at Google/Amazon/Meta?
Problems involving matrix symmetry, palindrome transformations, and pair matching frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests grid traversal, two-pointer reasoning, and recognizing independent symmetric pairs.
What data structure is used in Minimum Number of Flips to Make Binary Grid Palindromic I?
The problem primarily uses a 2D array (matrix). The algorithm performs index-based traversal and symmetric comparisons within rows and columns, often implemented with two-pointer scanning.
What is the time complexity of Minimum Number of Flips to Make Binary Grid Palindromic I?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. Each cell is examined at most once while comparing symmetric pairs in rows and columns. The algorithm uses O(1) additional space.

Ready to solve this problem?

Practice Minimum Number of Flips to Make Binary Grid Palindromic I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Moves to Make Palindrome