Problem statement

https://leetcode.com/problems/coloring-a-border/

Solution

Standard dfs/bfs problem with a bit strange statement: you need to deal carefuly with border of grid. When we have value (r, c) with color clr and its neighbour (i, j) with different color, we know that it is border.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def colorBorder(self, grid, r0, c0, color):
        m, n, clr = len(grid), len(grid[0]), grid[r0][c0]
        queue, V = deque([(r0, c0)]), {(r0, c0)}
        while queue:
            r, c = queue.popleft()
            if r in [0, m - 1] or c in [0, n - 1]:
                grid[r][c] = color
            for i, j in (r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c):
                if not 0 <= i < m or not 0 <= j < n or (i, j) in V: continue
                if grid[i][j] == clr:
                    V.add((i, j))
                    queue += [(i, j)]
                else:    
                    grid[r][c] = color
        return grid