Coloring A Border: DFS Component Boundary Detection

You are given an m x n integer grid, a starting cell (row, col), and a color value. Find the connected component containing (row, col) (all cells reachable by moving up, down, left, or right through cells with the same value). Then color the border of that component with the given color. A cell is a border cell if it is on the edge of the grid or if at least one of its 4-directional neighbors has a different value from the component.

This is LeetCode 1034: Coloring A Border, and it is a great exercise in combining DFS flood fill with boundary detection. The skills you build here, finding a connected component and reasoning about which cells touch the "outside," apply to problems like Surrounded Regions, Island Perimeter, and many other grid traversal challenges.

Why this problem matters

Grid problems frequently ask you to find connected components. That part is standard DFS or BFS. But this problem adds a twist: once you find the component, you need to figure out which cells are on its boundary and which are fully interior. That distinction, border versus interior, shows up whenever you need to compute perimeters, detect enclosed regions, or paint outlines.

Learning to separate "find the component" from "classify each cell" gives you a cleaner mental model. Instead of trying to do everything in one pass, you break the problem into two phases. That two-phase approach scales to harder problems where the classification logic gets more complex.

The key insight

First, use DFS to discover every cell in the connected component starting from (row, col). Store them in a set. Then, for each cell in the component, check whether it qualifies as a border cell. A cell is a border cell if:

1. It sits on the edge of the grid (its row is 0 or m-1, or its column is 0 or n-1), OR
2. At least one of its four neighbors has a value different from the component's original color.

If neither condition is true, the cell is interior, meaning all four of its neighbors are also part of the same component. Only border cells get recolored. Interior cells stay the same.

The solution

def color_border(grid: list[list[int]], row: int, col: int, color: int) -> list[list[int]]:
    rows, cols = len(grid), len(grid[0])
    original = grid[row][col]
    visited = set()
    component = []

    def dfs(r, c):
        if (r, c) in visited:
            return
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != original:
            return
        visited.add((r, c))
        component.append((r, c))
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    dfs(row, col)

    for r, c in component:
        is_border = False
        if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
            is_border = True
        else:
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if grid[r + dr][c + dc] != original:
                    is_border = True
                    break
        if is_border:
            grid[r][c] = color

    return grid

Let's walk through what each piece does.

The DFS explores outward from (row, col), collecting every cell that shares the original color and is connected to the start. We use a visited set to avoid revisiting cells, and we store the full component in a list for the second pass.

The second loop iterates over every cell in the component. For each one, it checks the two border conditions: is the cell on a grid edge, or does it have a neighbor with a different color? If either condition holds, we overwrite that cell with the new color. Interior cells are left untouched.

Notice that we check grid[r + dr][c + dc] != original rather than checking whether the neighbor is in the component. This works because if a neighbor has a different value in the original grid, it is definitionally outside the component. And since we have not modified the grid yet during the classification loop, the original values are still intact.

Visual walkthrough

Let's trace through the algorithm on a 3x4 grid starting from cell (1,1) with new color 3.

The DFS fans out from (1,1) and finds all 10 cells with value 1. Then the classification pass checks each cell. Only (1,1) has all four neighbors inside the component, making it the sole interior cell. Every other cell either sits on a grid edge or neighbors a cell with value 2. Those 9 border cells get recolored to 3, and (1,1) keeps its original value of 1.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. The DFS visits each cell at most once thanks to the visited set, so the exploration phase is proportional to the grid size. The classification phase iterates over the component cells (at most m * n) and checks four neighbors per cell, which is constant work per cell. Total: O(m * n).

Space is O(m * n) for the visited set, the component list, and the DFS recursion stack. In the worst case, the entire grid is one connected component, so all three data structures scale with the grid size.

The building blocks

1. DFS flood fill to find connected component

The core pattern: start from a cell, explore all 4-directional neighbors with the same value, and collect the full component.

def dfs(r, c):
    if (r, c) in visited:
        return
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    if grid[r][c] != original:
        return
    visited.add((r, c))
    component.append((r, c))
    dfs(r + 1, c)
    dfs(r - 1, c)
    dfs(r, c + 1)
    dfs(r, c - 1)

This is the same flood fill you use in Number of Islands, Flood Fill, and Surrounded Regions. The only difference is what you do with the component once you have it. Here, you classify cells as border or interior. In other problems, you count components, measure area, or check enclosure. The DFS skeleton stays the same.

2. Border cell identification

After collecting the component, classify each cell:

for r, c in component:
    is_border = False
    if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
        is_border = True
    else:
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if grid[r + dr][c + dc] != original:
                is_border = True
                break
    if is_border:
        grid[r][c] = color

The two conditions capture the two ways a cell can be on the boundary. Grid-edge cells are always borders because they face the "outside" of the grid. Non-edge cells are borders only if at least one neighbor belongs to a different region. This check is safe because we have not modified the grid yet, so all values reflect the original state.

Edge cases

Before submitting, think through these scenarios:

• New color equals original color: the answer is the unmodified grid. Every border cell gets "colored" with its current value, which is a no-op. The code handles this correctly without a special case.
• Single cell grid: the sole cell is both on the grid edge and the only member of its component. It is a border cell and gets recolored.
• Entire grid is one value: every cell is in the component. Only cells on the grid perimeter are borders. Interior cells stay unchanged.
• Component is a single row or column: every cell in a 1-wide component is on a grid edge, so all cells are borders.
• Starting cell is already a border cell: this does not affect the algorithm. You still find the full component and classify all cells.
• Component is a single cell surrounded by different values: that cell is a border (it has neighbors with different colors) and gets recolored.

From understanding to recall

You have seen how to split this problem into two clean phases: DFS to find the component, then a linear scan to classify borders and apply the color. The logic is not hard to understand. But reproducing it under pressure means remembering the details. Do you check the grid edges before or after checking neighbors? Do you modify the grid during DFS or after? Do you compare against the original color or the new color?

These small decisions trip people up when they have not practiced recently. Spaced repetition locks them in. You write the DFS flood fill from memory, then the border classification loop, at increasing intervals. After a few rounds, the two-phase pattern is automatic. You see "find a component and do something to its boundary" and the code flows out.

Related posts

• Flood Fill - The foundational DFS grid problem that teaches recursive exploration of connected cells
• Number of Islands - Uses the same DFS flood fill to count connected components in a grid
• Surrounded Regions - Another boundary detection problem where you identify cells on the border versus enclosed interior

CodeBricks breaks Coloring A Border into its DFS flood fill and border classification building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the two-phase pattern is automatic. When a grid boundary problem shows up in your interview, you do not think about it. You just write it.