We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove All Ones With Row and Column Flips

Number: 2268

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an m x n binary matrix grid, you can flip any row or column (i.e., change all 0's to 1's and all 1's to 0's). Determine whether it is possible to remove all 1's from grid (i.e., make every element 0) through any number of such operations.

Key Insights

  • Flipping rows and columns is commutative, and the order does not matter.
  • You can think of the operations as toggling the parity of each cell.
  • The relative relation between rows is critical; every row must either be identical to a reference row or be its bitwise complement.
  • If any row does not follow this pattern, it is impossible to achieve an all-zero matrix.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(1) extra space (ignoring input storage) as we use only constant additional storage.

Solution

The key idea is to choose the first row as a reference (base) row. For every row in the grid, check if it is identical to the base row or if it is its bitwise complement. This works because a valid flip sequence can convert the base row to all zeros, and if every other row is either the same or the complement, appropriate row or column flips can convert them as well. If any row deviates from this pattern, then it is impossible to achieve a complete zero matrix. This solution uses simple iteration and comparison, avoiding any complex data structures.

Code Solutions

# Define function to determine if grid can be transformed
def removeOnes(grid):
    m = len(grid)              # Number of rows
    n = len(grid[0])           # Number of columns
    base = grid[0]             # Use the first row as the reference row

    # Iterate over each row in the grid
    for row in grid:
        same = True            # Flag to check if the row is identical to base
        complement = True      # Flag to check if the row is the complement of base

        # Compare each element in the row with the corresponding element in the base
        for j in range(n):
            if row[j] != base[j]:
                same = False   # Not identical to base
            if row[j] != 1 - base[j]:
                complement = False   # Not complement of base
        
        # If the row is neither identical nor complement, return False
        if not (same or complement):
            return False

    return True  # All rows satisfy the relation, grid can be cleared

# Example usage:
grid = [[0,1,0],[1,0,1],[0,1,0]]
print(removeOnes(grid))  # Output: True
← Back to All Questions