LeetCode 2128 - Remove All Ones With Row and Column Flips

The problem gives us an m x n binary matrix named grid, where every cell contains either 0 or 1. We are allowed to perform two kinds of operations: 1. Flip an entire row 2. Flip an entire column Flipping means changing every 0 into 1 and every 1 into 0.

leetcodemediumarraymathbit-manipulationmatrix

LeetCode Problem 2128

Difficulty: 🟡 Medium
Topics: Array, Math, Bit Manipulation, Matrix

Solution

Problem Understanding

The problem gives us an m x n binary matrix named grid, where every cell contains either 0 or 1. We are allowed to perform two kinds of operations:

  1. Flip an entire row
  2. Flip an entire column

Flipping means changing every 0 into 1 and every 1 into 0.

Our goal is to determine whether it is possible to transform the entire matrix into all zeros after performing any number of row and column flips.

A very important detail is that row and column flips can be applied in any order and any number of times. Since flipping the same row or column twice cancels the effect, each row and column effectively has only two states: flipped or not flipped.

The constraints are:

  • 1 <= m, n <= 300
  • Each cell is either 0 or 1

Since the matrix can contain up to 300 x 300 = 90,000 cells, exponential exploration of all flip combinations is completely infeasible. We need a solution that runs roughly in polynomial time.

The key challenge is understanding what kinds of matrices can actually be converted into all zeros. Some matrices have a hidden consistency property that makes this possible, while others fundamentally cannot be fixed regardless of the sequence of flips.

Several edge cases are important:

  • A matrix that already contains all zeros should immediately return true
  • A single-cell matrix always works because we can flip its row or column if needed
  • Matrices where some rows partially match and partially differ from the first row are impossible to solve
  • Rectangular matrices must be handled correctly, not just square matrices

Approaches

Brute Force Approach

A brute force solution would try every possible combination of row flips and column flips.

There are m rows and n columns. Each one can either be flipped or not flipped, so there are:

$$2^m \times 2^n = 2^{m+n}$$

possible states to test.

For every combination, we would simulate all flips and check whether the final matrix contains only zeros.

This approach is correct because it exhaustively explores every possible sequence of operations. If a valid configuration exists, brute force will eventually find it.

However, this approach is far too slow. With m = n = 300, the number of combinations becomes astronomically large:

$$2^{600}$$

which is completely infeasible.

Key Insight

The important observation is that every row must be either:

  • Exactly equal to the first row
  • Exactly the inverse of the first row

Why?

Suppose we decide which columns to flip so that the first row becomes all zeros.

For every column:

  • If grid[0][j] == 1, we flip column j
  • Otherwise, we do not flip it

After these column flips, every row transforms according to its relationship with the first row.

If another row is identical to the first row, it also becomes all zeros.

If another row is the bitwise inverse of the first row, it becomes all ones, and then a single row flip converts it to all zeros.

But if a row differs from the first row in some positions and matches in others, then after column flips it becomes a mixed row containing both zeros and ones. No single row flip can fix that.

Therefore, every row must satisfy one of these conditions:

$$grid[i][j] = grid[0][j]$$

for all columns, or

$$grid[i][j] \ne grid[0][j]$$

for all columns.

This leads to a very clean linear-time solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n) * m * n) O(1) Tries every possible row and column flip combination
Optimal O(m * n) O(1) Checks whether every row matches or inverts the first row

Algorithm Walkthrough

  1. Store the first row as the reference pattern.

The entire matrix feasibility depends on how every other row relates to this row. 2. Iterate through every remaining row.

For each row, determine whether it is:

  • identical to the first row, or
  • the exact inverse of the first row
  1. Compare each element in the current row against the corresponding element in the first row.

The relationship between the current row and the first row must remain consistent across the entire row. 4. Use the first column to determine the expected relationship.

If:

$$grid[i][0] == grid[0][0]$$

then the entire row must match the first row.

Otherwise, the entire row must be inverted relative to the first row. 5. For every column j, verify consistency.

The following condition must hold:

$$grid[i][j] \oplus grid[i][0] = grid[0][j] \oplus grid[0][0]$$

This expression checks whether the equality or inequality relationship is preserved. 6. If any mismatch is found, immediately return false.

That means the row is neither identical nor inverted relative to the first row. 7. If all rows satisfy the condition, return true.

Why it works

The algorithm works because column flips affect every row equally. Once we decide how to transform the first row into all zeros, every other row becomes fully determined.

A row that matches the first row becomes all zeros after the same column flips.

A row that is the inverse of the first row becomes all ones, which can then be fixed with one row flip.

Any row that is partially matching and partially inverted becomes a mixed row that cannot be transformed into all zeros with a single row flip. Therefore, such matrices are impossible.

Python Solution

from typing import List

class Solution:
    def removeOnes(self, grid: List[List[int]]) -> bool:
        rows = len(grid)
        cols = len(grid[0])

        for row in range(rows):
            for col in range(cols):
                if (
                    grid[row][col] ^ grid[row][0]
                ) != (
                    grid[0][col] ^ grid[0][0]
                ):
                    return False

        return True

The implementation directly follows the mathematical observation from the algorithm.

The outer loop iterates through every row, while the inner loop checks every column.

The XOR expression:

grid[row][col] ^ grid[row][0]

captures whether the current cell matches the first element of its row.

Similarly:

grid[0][col] ^ grid[0][0]

captures whether the corresponding element in the first row matches the first element of the first row.

If these relationships differ, then the current row is neither identical nor inverted relative to the first row, so the matrix cannot be solved.

The algorithm immediately returns False when such a violation is found. Otherwise, after checking all cells, it returns True.

Go Solution

func removeOnes(grid [][]int) bool {
    rows := len(grid)
    cols := len(grid[0])

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if (grid[row][col]^grid[row][0]) !=
                (grid[0][col]^grid[0][0]) {
                return false
            }
        }
    }

    return true
}

The Go implementation is almost identical to the Python version.

Go uses the ^ operator for bitwise XOR just like Python. Since all values are binary (0 or 1), XOR cleanly expresses whether two values are equal or different.

No special handling for integer overflow is necessary because all operations involve only small integers. The matrix is represented using slices of slices, which naturally supports rectangular dimensions.

Worked Examples

Example 1

grid = [
    [0,1,0],
    [1,0,1],
    [0,1,0]
]

The first row is:

[0,1,0]

Now check every row.

Row Comparison Result
[0,1,0] identical
[1,0,1] inverse
[0,1,0] identical

Detailed XOR verification:

row col grid[row][col] ^ grid[row][0] grid[0][col] ^ grid[0][0] Match
0 0 0 ^ 0 = 0 0 ^ 0 = 0 yes
0 1 1 ^ 0 = 1 1 ^ 0 = 1 yes
0 2 0 ^ 0 = 0 0 ^ 0 = 0 yes
1 0 1 ^ 1 = 0 0 ^ 0 = 0 yes
1 1 0 ^ 1 = 1 1 ^ 0 = 1 yes
1 2 1 ^ 1 = 0 0 ^ 0 = 0 yes
2 0 0 ^ 0 = 0 0 ^ 0 = 0 yes
2 1 1 ^ 0 = 1 1 ^ 0 = 1 yes
2 2 0 ^ 0 = 0 0 ^ 0 = 0 yes

All checks pass, so the answer is:

true

Example 2

grid = [
    [1,1,0],
    [0,0,0],
    [0,0,0]
]

Reference row:

[1,1,0]

Check second row:

[0,0,0]

This row is neither identical nor inverse.

Verification:

col Current Expression Reference Expression Match
0 0 ^ 0 = 0 1 ^ 1 = 0 yes
1 0 ^ 0 = 0 1 ^ 1 = 0 yes
2 0 ^ 0 = 0 0 ^ 1 = 1 no

A mismatch occurs, so the answer is:

false

Example 3

grid = [[0]]

Single-cell matrix.

row col Expression Comparison
0 0 0 ^ 0 == 0 ^ 0

The check succeeds, so the answer is:

true

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell is visited exactly once
Space O(1) Only a few variables are used

The algorithm performs a constant amount of work for each matrix cell. Since the matrix contains m * n cells, the total running time is linear in the size of the input.

No additional data structures proportional to input size are allocated, so the auxiliary space complexity remains constant.

Test Cases

sol = Solution()

assert sol.removeOnes([[0,1,0],[1,0,1],[0,1,0]]) == True
# Basic valid example with inverse rows

assert sol.removeOnes([[1,1,0],[0,0,0],[0,0,0]]) == False
# Invalid matrix from problem statement

assert sol.removeOnes([[0]]) == True
# Single zero cell

assert sol.removeOnes([[1]]) == True
# Single one cell can be flipped

assert sol.removeOnes([[0,0,0]]) == True
# Single row already all zeros

assert sol.removeOnes([[1,1,1]]) == True
# Single row can always be flipped

assert sol.removeOnes([[0],[1],[0],[1]]) == True
# Single column always solvable

assert sol.removeOnes([
    [0,1],
    [1,0]
]) == True
# Perfect inverse rows

assert sol.removeOnes([
    [0,1],
    [1,1]
]) == False
# Partial mismatch prevents solution

assert sol.removeOnes([
    [1,0,1,0],
    [0,1,0,1],
    [1,0,1,0]
]) == True
# Larger valid alternating pattern

assert sol.removeOnes([
    [1,0,1],
    [0,1,0],
    [1,1,0]
]) == False
# One inconsistent row breaks feasibility

assert sol.removeOnes([
    [0,0,1],
    [1,1,0],
    [0,0,1],
    [1,1,0]
]) == True
# Multiple repeated inverse patterns

Test Summary

Test Why
[[0,1,0],[1,0,1],[0,1,0]] Standard valid example
[[1,1,0],[0,0,0],[0,0,0]] Standard invalid example
[[0]] Smallest possible matrix
[[1]] Single cell requiring flip
[[0,0,0]] Single-row trivial success
[[1,1,1]] Entire row can be flipped
[[0],[1],[0],[1]] Single-column handling
[[0,1],[1,0]] Exact inverse rows
[[0,1],[1,1]] Partial mismatch case
Larger alternating pattern Confirms repeated valid structure
Inconsistent mixed row Confirms failure detection
Repeated inverse patterns Ensures scalability across many rows

Edge Cases

One important edge case is a matrix containing only a single cell. A naive implementation might overcomplicate the logic or accidentally assume at least two rows or columns exist. In reality, both [[0]] and [[1]] are always solvable because we can either do nothing or flip the row or column once. The implementation handles this naturally because the XOR comparisons still work correctly for a 1 x 1 matrix.

Another important edge case is a matrix with only one row or only one column. In these situations, every configuration is solvable because individual columns or rows can always be flipped independently to eliminate all ones. The implementation correctly returns True because every row is trivially identical or inverse relative to the first row.

A particularly tricky edge case occurs when a row partially matches the first row and partially differs from it. For example:

[
    [1,0,1],
    [1,1,0]
]

The second row is neither identical nor fully inverted relative to the first row. After any sequence of column flips, the row will still contain a mixture of zeros and ones, making it impossible to eliminate all ones with a single row flip. The XOR consistency check detects this immediately.

Another subtle edge case involves repeated patterns across many rows. Some incorrect solutions try to greedily flip rows or columns and may accidentally depend on operation order. The mathematical invariant used here avoids that issue entirely because it checks the structural property that determines solvability, independent of any specific sequence of flips.