Remove All Ones With Row and Column Flips

Remove All Ones With Row and Column Flips - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[0,1],[0,1]]

› Output: true

💡 Note: Both rows are identical [0,1]. We can flip column 1 to make all rows [0,0], then they're all zeros.

Example 2 — Complementary Rows

$ Input: grid = [[0,1],[1,0]]

› Output: true

💡 Note: Row 2 is the complement of Row 1. We can flip all columns to make both rows [1,0], then flip both rows to get all zeros.

Example 3 — Impossible Case

$ Input: grid = [[0,0],[1,1],[0,1]]

› Output: false

💡 Note: Row 3 [0,1] is neither identical nor complementary to Row 1 [0,0]. Cannot be made consistent through flips.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 1's and 0's

Apply Flips

Strategically flip rows and columns

Result Check

Determine if all 1's can be removed

Key Takeaway

🎯 Key Insight: A matrix can be cleared if all rows are either identical or complete complements of each other

Asked in

G Google 15 a Amazon 8 M Microsoft 12

The key insight is that after optimal row flips, all rows must be either identical or complete complements of each other. The Row Pattern Analysis approach checks if all rows are identical or complementary to the first row in O(m×n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Row Pattern Analysis	O(m × n)	O(1)	Check if all rows can be made identical or complementary
Brute Force - Try All Flip Combinations	O(2^(m+n) × m × n)	O(m × n)	Try all possible combinations of row and column flips

Row Pattern Analysis — Algorithm Steps

Step 1: Consider first row as target (flip to all zeros if needed)
Step 2: For each other row, check if it can match target via column flips
Step 3: A row matches if it's identical or completely opposite to target

Visualization

Tap to expand

Step-by-Step Walkthrough

Reference Row

Use first row as reference pattern

Compare Rows

Check if each row is identical or opposite to first row

Validate

If all rows match pattern, matrix can be cleared

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int m, int n) {
    if (m == 0 || n == 0) return 1;
    
    int* firstRow = grid[0];
    
    // Check if all rows are either identical to first row or completely opposite
    for (int i = 1; i < m; i++) {
        // Check if current row matches first row (identical)
        int matches = 1;
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != firstRow[j]) {
                matches = 0;
                break;
            }
        }
        
        if (matches) continue;
        
        // Check if current row is opposite to first row
        int opposite = 1;
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == firstRow[j]) {
                opposite = 0;
                break;
            }
        }
        
        if (!opposite) return 0;
    }
    
    return 1;
}

int main() {
    // Simplified input parsing
    int grid[20][20];
    int m = 2, n = 2; // Example
    int* gridPtrs[20];
    for (int i = 0; i < m; i++) {
        gridPtrs[i] = grid[i];
    }
    
    int result = solution(gridPtrs, m, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Single pass through matrix to compare each row with first row

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for comparison

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Row Pattern Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler