Minimum Number Of Flips To Convert Binary Matrix To Zero Matrix - Leetcode Solution

Problem Statement:

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours 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 in which all elements are either 0 or 1.

Solution:

The problem can be solved using breadth first search (BFS). The algorithm is as follows:

• Create a queue to store the matrix and a set to store the visited states.
• Add the initial state of the matrix to the queue and mark it as visited.
• While the queue is not empty, perform the following steps:
  • Pop the next element from the queue and check if it’s a zero matrix. If yes, return the number of flips taken.
  • Otherwise, for each cell in the matrix, flip it and its neighbours, and add the resulting matrix to the queue if it’s not visited before.
  • If there’s no such matrix, return -1 as it’s not possible to convert the matrix into a zero matrix.

The time complexity of the algorithm is O(mn2^(mn)), where m and n are the dimensions of the matrix. This is because the maximum number of states or matrices that can be generated is 2^(mn). The space complexity is O(2^(m*n)) as we need to store all the states to ensure that we don’t visit the same state twice.

Code:

Here’s the Python code for the algorithm:

from collections import deque

class Solution:
    # function to flip a cell and its neighbours
    def flip(self, x, y, mat):
        for dx, dy in [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(mat) and 0 <= ny < len(mat[0]):
                mat[nx][ny] ^= 1  # bitwise XOR to flip the cell

    def minFlips(self, mat: List[List[int]]) -> int:
        queue = deque()
        visited = set()

        # convert the matrix to a tuple and add it to the queue
        queue.append((tuple(map(tuple, mat)), 0))
        visited.add(tuple(map(tuple, mat)))

        while queue:
            curr, flips = queue.popleft()

            # check if the matrix is a zero matrix
            if all(all(c == 0 for c in row) for row in curr):
                return flips

            # Try flipping each cell and then check if the resulting matrix is a new state.
            for i in range(len(curr)):
                for j in range(len(curr[0])):
                    temp = list(list(row) for row in curr)  # deepcopy
                    self.flip(i, j, temp)
                    temp_t = tuple(map(tuple, temp))
                    if temp_t not in visited:
                        queue.append((temp_t, flips + 1))
                        visited.add(temp_t)

        return -1

The function flip is used to flip a cell and its neighbours. The function converts the matrix to a tuple of tuples before adding it to the queue as sets cannot be hashed.

1