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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is either 0 or 1.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.
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,0,0,1, the other row is also 1,0,0,1;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:
0, keep the row unchanged;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:
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Flip Simulation | O(2^(m+n) * m*n) | O(1) | Conceptual understanding of the flip operations and search space |
| Row Pattern Normalization with Hash Table | O(m*n) | O(n) | Optimal approach for interviews and large matrices |
Leetcode 2128 | Remove All Ones With Row and Column Flips | Google • Mike the Coder • 3,374 views views
Watch 3 more video solutions →Practice Remove All Ones With Row and Column Flips with our built-in code editor and test cases.
Practice on FleetCode