Leetcode: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Problem Statement

Understand the problem

Modeling as graph problem, the problem is to Pattern: Find shortest path between two vertices in a graph. A binary matrix is a vertex and two binary matrices are connected if you can flip one of it's cells and get from one to the other. There are at most \(2^{n \times m }= 2^9 = 512\) vertices with 4 edges ending on each one of them.

Devise a plan (1)

A Breadth-first search from the given binary matrix to the zero matrix is enough to solve the problem, since there are no costs associated to the edges. Time and space complexity are \(O(2^{n \times m})\), given that the Pattern: Small constraints allows the representation of the binary matrix using at most \(3 \times 3\) bits.

Carry out the plan

from typing import List


class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        N = len(mat)
        M = len(mat[0])

        def id(i, j):
            return 1 << (i * M + j)

        initial = 0
        for i in range(N):
            for j in range(M):
                if mat[i][j] == 1:
                    initial = initial | id(i, j)

        seen = set()
        queue = [(0, initial)]

        for steps, state in queue:
            if state == 0:
                return steps
            if state in seen:
                continue
            seen.add(state)

            for i in range(N):
                for j in range(M):
                    nstate = state
                    for di, dj in [[+0, +0], [+0, +1], [+0, -1], [+1, +0], [-1, +0]]:
                        if 0 <= di + i < N and 0 <= dj + j < M:
                            if nstate & id(di + i, dj + j) != 0:
                                nstate = nstate & ~id(di + i, dj + j)
                            else:
                                nstate = nstate | id(di + i, dj + j)
                    queue.append((steps + 1, nstate))
        return -1


assert Solution().minFlips([[0, 0], [0, 1]]) == 3
assert Solution().minFlips([[0]]) == 0
assert Solution().minFlips([[1, 0, 0], [1, 0, 0]]) == -1

Devise a plan (2)

A Depth-first search can be used to search the minimum number of flips given an instance \((m, i, j)\) of the problem where \(m\) is a binary matrix, and \(i,j\) is a cell position. Optimization: We don't need to flip all cells but only cells on the first row or ones that will make the above cell a zero (inspired on StefanPochamann's solution). There are \(O(2^{n \times m} \times n \times m)\) with \(5\) possible transitions (Pattern: Small constraints).

Carry out the plan

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        N = len(mat)
        M = len(mat[0])
        D = [[+1, +0], [-1, +0], [+0, +1], [+0, -1]]
        S = 0

        bit = lambda i, j: 1 << (i * M + j)
        flip = lambda state, i, j: state | bit(i, j) if state & bit(i, j) == 0 else state & ~bit(i, j)

        for i in range(N):
            for j in range(M):
                if mat[i][j] == 1:
                    S = flip(S, i, j)

        def dfs(state, i, j):
            if i == N:
                return 0 if state == 0 else float("inf")
            if j == M:
                return dfs(state, i + 1, 0)
            ans = dfs(state, i, j + 1)
            nstate = flip(state, i, j)
            for di, dj in D:
                ni, nj = i + di, j + dj
                if 0 <= ni < N and 0 <= nj < M:
                    nstate = flip(nstate, ni, nj)
            if i == 0 or bit(i - 1, j):
                ans = min(ans, 1 + dfs(nstate, i, j + 1))
            return ans

        ans = dfs(S, 0, 0)
        return -1 if ans == float("inf") else ans

Common mistakes