Remove All Ones With Row and Column Flips

Medium
917.

Remove All Ones With Row and Column Flips

Remove All Ones With Row and Column Flips is a medium coding problem on arrays, matrix and bit manipulation, asked in Amazon, Google and Salesforce interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var removeOnes = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove All Ones With Row and Column Flips — Solution

Remove All Ones With Row and Column Flips solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Remove All Ones With Row and Column Flips is a medium coding problem on arrays, matrix and bit manipulation, asked in Amazon, Google and Salesforce interviews.

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

Hints for Remove All Ones With Row and Column Flips

  1. Hint 1

    Flips commute, and flipping the same line twice undoes itself, so only the parity of each row and column flip matters.

  2. Hint 2

    Compare every row with the first row.

  3. Hint 3

    Each row must be either identical to the first or its exact complement.

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

  1. For each row i > 0, look at whether grid[i][0] matches grid[0][0].
  2. Require the same relationship (match or mismatch) in every column of that row.
  3. 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

Java

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

C++

bool removeOnes(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    for (int i = 1; i < m; i++) {
        bool same = grid[i][0] == grid[0][0];
        for (int j = 0; j < n; j++) {
            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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal