Coloring A Border - Leetcode Solution

The "Coloring A Border" problem on LeetCode can be solved using a Depth-First-Search (DFS) approach. In this problem, we are given a 2D grid and we are supposed to color the boundary of a given cell (r0, c0) and all its neighboring cells which have the same color as the given cell with a new color.

The main idea is to traverse the grid and mark all the cells which are on the border with the given color. To do this, we can use a recursive DFS approach. Here are the detailed steps:

1. Initialize a visited array for all the cells in the grid and mark all cells to be unvisited.
2. Initialize queue with the given cell, (r0, c0).
3. While the queue is not empty: a. Pop the first cell from the queue. b. If the cell is already visited or is not of the given color, skip to the next iteration. c. If the cell is on the border of the grid, color it with the given new color and mark the cell as visited. d. Otherwise, mark the current cell as visited, and add all unvisited neighboring cells with the same color to the queue.
4. Return the updated grid.

Here is the Python code implementation of the above algorithm:

class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        # Define the size of the grid
        m, n = len(grid), len(grid[0])
        # Define direction vectors for movement in four directions
        dxdy = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        # Initialize visited array
        visited = [[False] * n for _ in range(m)]
        
        # Define recursive DFS function
        def dfs(x: int, y: int, c: int) -> bool:
            # If the current cell is on the border of the grid, mark it as visited and color it with the new color
            if x == 0 or x == m - 1 or y == 0 or y == n - 1:
                visited[x][y] = True
                grid[x][y] = c
                return True
            # Mark the current cell as visited
            visited[x][y] = True
            # Check all four neighboring cells
            for dx, dy in dxdy:
                nx, ny = x + dx, y + dy
                # If the neighboring cell is within the grid and has the same color, add it to the queue
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == c and not visited[nx][ny]:
                    if dfs(nx, ny, c):
                        # If the neighboring cell is on the border, color the current cell with the new color
                        grid[x][y] = c
                        return True
            return False
        
        # Call the DFS function
        dfs(r0, c0, grid[r0][c0])
        # Return the updated grid
        return grid

The time complexity of this algorithm is O(m * n) where m and n are the dimensions of the given grid.

1