Problem statement

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/

Solution

The simplest approach is bfs, where for each state we try all possible flips and add them to queue.

Complexity

Time complexity is O(mn*2^(mn)), space is potentially the same.

Code

class Solution:
    def minFlips(self, mat):
        m, n = len(mat), len(mat[0])
        Q, v = deque([(0, mat)]), set()
        
        while Q:
            steps, mat = Q.popleft()
            if sum(chain(*mat)) == 0: return steps
            
            for x, y in product(range(n), range(m)):
                mat2 = [row[:] for row in mat]
                for dx, dy in [[x, y], [x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
                    if 0 <= dx < n and 0 <= dy < m:
                        mat2[dy][dx] = 1 - mat2[dy][dx]
                        
                mat2t = tuple(map(tuple, mat2))
                if mat2t not in v:
                    v.add(mat2t)
                    Q.append((steps + 1, mat2))
        
        return -1

Remark

Another possible approaches:

  1. Note that it does not matter which order we do flips, so let us start from top row. Actually top row uniquely define all flips, so complexity will be O(mn*2^n)
  2. Also the is linear algebra solution with O(m^3n^3) solution, but it is quite difficult to code.