Skip to main content
Talentd

Remove All Ones With Row and Column Flips - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathBit ManipulationMatrix12 min readAsked at: Google
Practice this problem

Problem Statement

You are given an m x n binary matrix grid.

In one operation, you can choose any row or column and flip each value in that row or column (i.e., changing all 0's to 1's, and all 1's to 0's).

Return true if it is possible to remove all 1's from grid using any number of operations or false otherwise.

 

Example 1:

Input: grid = [[0,1,0],[1,0,1],[0,1,0]]
Output: true
Explanation: One possible way to remove all 1's from grid is to:
- Flip the middle row
- Flip the middle column

Example 2:

Input: grid = [[1,1,0],[0,0,0],[0,0,0]]
Output: false
Explanation: It is impossible to remove all 1's from grid.

Example 3:

Input: grid = [[0]]
Output: true
Explanation: There are no 1's in grid.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is either 0 or 1.

Approach Overview

Problem Overview: You are given a binary matrix where you can flip any row or column (toggle 0 ↔ 1). The task is to determine whether a sequence of flips can transform the matrix so that every cell becomes 0.

Approach 1: Brute Force Flip Simulation (Exponential Time)

The naive idea tries combinations of row and column flips and checks whether the matrix becomes all zeros. Each row or column can be flipped or not, so you effectively explore subsets of flips. For an m x n matrix this leads to up to 2^(m+n) possibilities, and each configuration requires scanning the grid in O(m*n). Total complexity becomes O(2^(m+n) * m*n) time with O(1) extra space. This approach is impractical for even moderate grid sizes but helps reveal a useful property: flipping a column affects every row uniformly.

Approach 2: Row Pattern Normalization with Hashing (O(m*n))

The key observation is that column flips apply to every row equally. Because of that, rows must share the same pattern up to inversion. If one row becomes all zeros after some column flips, every other row must either match that row exactly or be its bitwise complement (which can then be fixed by flipping the entire row).

Normalize each row relative to its first element. If the first element is 1, invert the entire row; if it is 0, keep it unchanged. This transformation ensures every row starts with 0. After normalization, all rows must be identical for the matrix to be convertible to all zeros. Use a hash set or compare against the first normalized row while iterating.

You iterate through each cell once, giving O(m*n) time complexity and O(n) space for storing the normalized pattern. The logic relies on simple XOR or bit comparisons, which fits naturally with bit manipulation and array operations while scanning the matrix.

Recommended for interviews: The row normalization approach using hashing is the expected solution. Interviewers want to see the insight that column flips enforce a global pattern across rows. Mentioning the brute-force idea briefly shows you understand the search space, but recognizing the complement pattern reduces the problem to a linear scan and demonstrates stronger algorithmic reasoning.

Solution

We observe that if two rows in the matrix satisfy one of the following conditions, they can be made equal by flipping certain columns:

  1. The corresponding elements of the two rows are equal, i.e., if one row is 1,0,0,1, the other row is also 1,0,0,1;
  2. The corresponding elements of the two rows are opposite, i.e., if one row is 1,0,0,1, the other row is 0,1,1,0.

We call two rows that satisfy one of the above conditions "equivalent rows." The answer to the problem is the maximum number of equivalent rows in the matrix.

Therefore, we can traverse each row of the matrix and convert each row into an "equivalent row" that starts with 0. Specifically:

  • If the first element of the current row is 0, keep the row unchanged;
  • If the first element of the current row is 1, flip every element in the row, i.e., 0 becomes 1, 1 becomes 0. In other words, we flip rows starting with 1 into "equivalent rows" starting with 0.

In this way, we only need to use a hash table to count each converted row. If the hash table contains only one element at the end, it means we can remove all 1s from the matrix by flipping rows or columns.

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

Related problem:

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Flip SimulationO(2^(m+n) * m*n)O(1)Conceptual understanding of the flip operations and search space
Row Pattern Normalization with Hash TableO(m*n)O(n)Optimal approach for interviews and large matrices

Video Solution

Leetcode 2128 | Remove All Ones With Row and Column Flips | Google • Mike the Coder • 3,407 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Remove All Ones With Row and Column Flips easy or hard?
The problem is rated Medium because the implementation is simple but the insight about row complements is not immediately obvious. Once you realize every row must match the first row or its inverse, the solution becomes a straightforward O(m*n) scan.
Remove All Ones With Row and Column Flips Python/Java solution
Implement the normalization approach: for each row, flip the bits logically if the first element is 1, then compare the transformed row with a reference row. The same logic works across Python, Java, C++, Go, TypeScript, and Rust because it only requires iteration and simple bit checks.
How to solve Remove All Ones With Row and Column Flips in O(n)?
For an m x n matrix, the best achievable complexity is O(m*n) because every element must be inspected. Normalize each row by XORing with its first element so the row starts with 0. After normalization, verify that every row matches the same pattern as the first row.
What is the best approach for Remove All Ones With Row and Column Flips?
The optimal solution normalizes each row relative to its first element and checks whether all rows share the same normalized pattern. A row that starts with 1 is inverted so it matches the form of rows starting with 0. If every normalized row is identical, column flips can align them and row flips can remove remaining ones. This runs in O(m*n) time.
Is Remove All Ones With Row and Column Flips asked at Google/Amazon/Meta?
Matrix pattern and flip transformation problems appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests recognition of row complement patterns and efficient matrix traversal, both common interview themes.
What data structure is used in Remove All Ones With Row and Column Flips?
The common implementation uses a hash set or direct pattern comparison. Rows are normalized into a canonical form and stored or compared, making the hash table useful for quickly verifying that all patterns are identical.
What is the time complexity of Remove All Ones With Row and Column Flips?
The optimal algorithm scans each cell once while normalizing row patterns, giving O(m*n) time complexity for an m by n matrix. Space complexity is O(n) to store the reference row pattern or hash representation.

Ready to solve this problem?

Practice Remove All Ones With Row and Column Flips with our built-in code editor and test cases.

Practice on FleetCode
Previous

Difference Between Ones and Zeros in Row and Column

Next

Minimum Number of Flips to Convert Binary Matrix to Zero Matrix