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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Number: 1409

Difficulty: Hard

Paid? No

Companies: Airbnb

Problem Description

Given an m x n binary matrix, each cell is either 0 or 1. In one step, you can pick any cell and flip it along with its immediate neighbors (up, down, left, right). The "flip" operation toggles a cell’s value (0 changes to 1 and 1 changes to 0). The goal is to determine the minimum number of steps required to convert the matrix into a zero matrix (i.e., all cells are 0). If it is impossible, return -1.

Key Insights

  • The matrix has a small size (max 3 x 3), which means at most 9 cells. Therefore, the total number of states is limited (at most 2^9 = 512 states).
  • The problem can be modeled as a state-space search where each state is represented by a bitmask.
  • Breadth First Search (BFS) is ideal for finding the minimum number of steps because it explores all possible moves level by level.
  • For each state, flipping a cell will toggle it and its valid neighbors. Precompute all flip effects if needed.
  • Make sure to check for the goal state (all zeros) to terminate early.

Space and Time Complexity

Time Complexity: O(2^(mn) * (mn)), since there are at most 2^(mn) states and each state considers at most mn possible flips. Space Complexity: O(2^(m*n)), required for storing the visited states.

Solution

We solve the problem by using BFS. Each matrix state is represented as an integer bitmask. Each bit in the mask corresponds to a cell in the matrix. The BFS starts from the initial state derived from the matrix. For each state, we try to flip every cell one by one by toggling the chosen cell and its neighbors. We generate a new state and continue the BFS until we find the state representing the zero matrix, or we exhaust all possibilities. The BFS ensures that we get the minimum number of moves.

Data structures used:

  • Queue for BFS exploration.
  • Set or array to mark visited states, to avoid repetition.

Algorithm steps:

  1. Convert the matrix to an integer bitmask to represent the initial state.
  2. If the initial state is already zero, return 0.
  3. Initialize a queue for BFS and add the initial state.
  4. For each state in the BFS, iterate over all possible cell flips.
  5. Compute the new state by flipping the corresponding bits for the chosen cell and all valid neighbors.
  6. If the new state is zero, return the number of moves.
  7. If not visited, mark the new state as visited and add it to the queue.
  8. If the queue is exhausted without reaching zero, return -1.

Code Solutions

# Python solution using BFS and bit manipulation
from collections import deque

def minFlips(mat):
    # Dimensions of the matrix
    m, n = len(mat), len(mat[0])
    
    # Convert matrix to an integer bitmask
    start = 0
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 1:
                start |= (1 << (i * n + j))
    
    # If already a zero matrix, return 0 steps
    if start == 0:
        return 0
    
    # Directions for flipping: self, up, down, left, right
    directions = [(0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)]
    
    # BFS initialization
    queue = deque([start])
    visited = {start}
    steps = 0
    
    # BFS to explore all states
    while queue:
        steps += 1
        for _ in range(len(queue)):
            current = queue.popleft()
            # Try flipping each cell in the matrix
            for i in range(m):
                for j in range(n):
                    next_state = current
                    # Flip the current cell and its neighbors using bitmask
                    for dx, dy in directions:
                        x, y = i + dx, j + dy
                        if 0 <= x < m and 0 <= y < n:
                            next_state ^= (1 << (x * n + y))
                    # If we reached the zero matrix, return the steps count
                    if next_state == 0:
                        return steps
                    # Continue BFS if this state hasn't been seen
                    if next_state not in visited:
                        visited.add(next_state)
                        queue.append(next_state)
    return -1
← Back to All Questions