Watch 4 video solutions for Remove All Ones With Row and Column Flips, a medium level problem involving Array, Math, Bit Manipulation. This walkthrough by Mike the Coder has 3,374 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |