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 II

Number: 2314

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an m x n binary matrix grid, you can perform operations where you select a cell (i, j) that contains a 1 and change all the cells in row i and column j to 0. The goal is to determine the minimum number of operations required to remove all 1's from grid.

Key Insights

  • Since m * n ≤ 15, the total number of cells is small, which allows using a bitmask representation of the grid.
  • Each grid state can be encoded as an integer bitmask where each bit represents the state (0 or 1) of a cell.
  • Precompute an operation mask for each cell. When choosing a cell (i, j) with value 1, use the mask corresponding to row i and column j to clear these bits.
  • Use Breadth-First Search (BFS) to explore all possible grid states from the initial configuration until the target state (all zeros) is reached.
  • Use a visited set to avoid revisiting states.

Space and Time Complexity

Time Complexity: O(2^(mn) * (mn)) in the worst-case since we explore all possible states and for each state consider every cell operation. Space Complexity: O(2^(m*n)) due to the storage needed for the visited states.

Solution

We represent the grid as a bitmask integer where each bit corresponds to a cell. The bit is set to 1 if the cell contains a 1, and 0 otherwise. For each cell (i, j), precompute a mask that covers all indices in row i and column j. Then, perform a BFS starting from the initial bitmask, applying all valid operations (i.e. operations that target a 1 bit) to generate new states. The BFS ensures that the first time we encounter the state where all bits are 0 (i.e., no 1's remain) the current level represents the minimum number of operations.

Key Data Structures and Algorithms:

  • Bitmask representation for grid state.
  • Precomputed operation masks for each cell.
  • BFS using a queue for level order traversal.
  • A visited set/dictionary to track previously seen bitmask states and avoid redundant work.

Code Solutions

from collections import deque

def removeOnes(grid):
    m = len(grid)
    n = len(grid[0])
    total_cells = m * n

    # Function to map (i, j) to bitmask index
    def pos(i, j):
        return i * n + j

    # Convert grid to bitmask integer
    start = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                start |= (1 << pos(i, j))
    
    # Precompute the mask for each cell, which clears all ones in row i and column j.
    op_masks = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            mask = 0
            # Add all cells from row i
            for col in range(n):
                mask |= (1 << pos(i, col))
            # Add all cells from column j
            for row in range(m):
                mask |= (1 << pos(row, j))
            op_masks[i][j] = mask

    # BFS to find the minimum number of operations.
    queue = deque()
    queue.append((start, 0))  # (state, operations count)
    visited = set()
    visited.add(start)

    while queue:
        state, ops = queue.popleft()
        # Check if grid has no 1's
        if state == 0:
            return ops

        # Try using every cell as potential operation.
        for i in range(m):
            for j in range(n):
                # Only consider this operation if cell (i,j) is currently 1
                if state & (1 << pos(i, j)):
                    # Operation: set row i and column j to 0
                    new_state = state & ~op_masks[i][j]
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append((new_state, ops + 1))
                        
    return -1  # Should not reach here as a solution always exists.

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