Remove All Ones With Row and Column Flips — Medium Problem & Solution

A binary grid is given. In one operation you may pick any row or any column and flip every cell in it (0 becomes 1 and 1 becomes 0).

Difficulty: Medium
Topics: Arrays, Matrix, Bit Manipulation
Asked at: Amazon, Google, Salesforce
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A binary grid is given. In one operation you may pick any row or any column and flip every cell in it (0 becomes 1 and 1 becomes 0).

Return true if some sequence of operations can turn the whole grid into zeros.

Example 1

Input: grid = [[0,1,0],[1,0,1],[0,1,0]]
Output: true
Explanation: Flip the middle row, then the middle column, then the middle row again.

Example 2

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

Example 3

Input: grid = [[0]]
Output: true
Explanation: Already all zeros.

Constraints

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

How to solve Remove All Ones With Row and Column Flips

Since flips commute and are self-inverse, the answer depends only on which rows and which columns get flipped an odd number of times. That forces every row to be either equal to row 0 or its complement.

Approach

For each row i > 0, look at whether grid[i][0] matches grid[0][0].
Require the same relationship (match or mismatch) in every column of that row.
If any row is neither a copy nor a complement of row 0, return false; otherwise true.

Why it works

Let r_i and c_j be the flip parities. Clearing the grid means grid[i][j] XOR r_i XOR c_j = 0 for every cell, so grid[i][j] = r_i XOR c_j. Fixing r_0 = 0 determines c_j = grid[0][j], and then row i is forced to be row 0 XOR r_i — exactly "equal or complemented". Conversely, any grid of that shape is cleared by those parities, so the condition is both necessary and sufficient.

Complexity

Time — O(m · n)
Space — O(1)

Pitfalls

Simulating flips and searching is exponential; the algebra collapses it to one pass.
Rows must be uniformly equal or uniformly complemented — a mix fails.
A single row or a single column grid is always clearable.

Reference solution

Python

from typing import List

def removeOnes(grid: List[List[int]]) -> bool:
    m, n = len(grid), len(grid[0])
    for i in range(1, m):
        same = grid[i][0] == grid[0][0]
        for j in range(n):
            if (grid[i][j] == grid[0][j]) != same:
                return False
    return True

JavaScript

var removeOnes = function(grid) {
    var m = grid.length, n = grid[0].length;
    for (var i = 1; i < m; i++) {
        var same = grid[i][0] === grid[0][0];
        for (var j = 0; j < n; j++) {
            if ((grid[i][j] === grid[0][j]) !== same) return false;
        }
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue