Problem statement

https://binarysearch.com/problems/Color-Map/

Solution

We need to find connected components of graph, then for each color we need to know how many components of this color we have. In the end we will color all components to this color.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        if not M: return 0
        m, n = len(M), len(M[0])

        def dfs(x, y, c):
            if not 0 <= x < m or  not 0 <= y < n or M[x][y] == -1: return 

            if M[x][y] == c:
                M[x][y] = -1
                for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]: 
                    dfs(x + dx, y + dy, c)

        d = Counter()
        for x in range(m):
            for y in range(n):
                if M[x][y] == -1: continue
                d[M[x][y]] += 1
                dfs(x, y, M[x][y])

        vals = list(d.values())
        return sum(vals) - max(vals)