Problem statement

https://binarysearch.com/problems/Grid-Coloring/

Solution

What is asked is this problem is to find connected components, and then we need to find distance between these connected components. We can do in smarter way: If we say than we change color we pay 1 and if we do not change, we pay 0, then what we need to find is the biggest distance with these rules. We can either use Dijkstra or 0-1 bfs, which works faster.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        n, m = len(M), len(M[0])
        dist = [[-1] * m for i in range(n)]
        Q = deque([(0, 0)])
        dist[0][0] = 0
        
        while Q:
            x, y = Q.popleft()
            for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= i < n and 0 <= j < m and dist[i][j] == -1:
                    if M[x][y] == M[i][j]:
                        dist[i][j] = dist[x][y]
                        Q.appendleft((i, j))
                    else:
                        dist[i][j] = dist[x][y] + 1
                        Q.append((i, j))
        
        return max(max(i) for i in dist)