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

Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Difficulty: Hard

Problem Description

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighbors if they share one edge. Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot. A binary matrix is a matrix with all cells equal to 0 or 1 only. A zero matrix is a matrix with all cells equal to 0.

Key Insights

  • Flipping a cell affects not only that cell but also its four adjacent neighbors.
  • The maximum size of the matrix is 3x3, which allows for exhaustive search methods.
  • Each configuration of the matrix can be represented as a binary number, simplifying state representation.
  • The problem can be approached using Breadth-First Search (BFS) to explore all possible states.

Space and Time Complexity

Time Complexity: O(2^(mn)), where m and n are the dimensions of the matrix.
Space Complexity: O(2^(mn)), due to the storage of visited states in the BFS.

Solution

To solve the problem, we can use a Breadth-First Search (BFS) approach. We represent the matrix as a binary number to efficiently store and manipulate states. The BFS will explore all possible states by flipping cells and their neighbors, tracking the number of flips until we reach a zero matrix or exhaust all possibilities. If we reach the zero matrix, we return the count of flips; if not, we return -1.

Code Solutions

from collections import deque

def minFlips(mat):
    def to_tuple(matrix):
        return tuple(tuple(row) for row in matrix)

    def flip(matrix, i, j):
        directions = [(0, 0), (1, 0), (0, 1), (-1, 0), (0, -1)]
        for dx, dy in directions:
            if 0 <= i + dx < len(matrix) and 0 <= j + dy < len(matrix[0]):
                matrix[i + dx][j + dy] ^= 1  # Flip the cell
        return matrix

    target = [[0] * len(mat[0]) for _ in range(len(mat))]
    initial_state = to_tuple(mat)
    target_state = to_tuple(target)

    queue = deque([(initial_state, 0)])  # (current state, steps)
    visited = {initial_state}

    while queue:
        current, steps = queue.popleft()
        
        if current == target_state:
            return steps
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                new_matrix = [list(row) for row in current]
                new_matrix = flip(new_matrix, i, j)
                new_state = to_tuple(new_matrix)

                if new_state not in visited:
                    visited.add(new_state)
                    queue.append((new_state, steps + 1))
    
    return -1
← Back to All Questions