LeetCode 1034: Coloring A Border

Problem Restatement

We are given an m x n integer matrix grid and three integers row, col, and color.

We need to color the border of the connected component that contains cell (row, col) with the given color.

A border cell of a connected component is any cell that is either on the edge of the grid or has at least one neighbor that is not in the same connected component.

Return the final grid.

The official constraints state that 1 <= m, n <= 50, 1 <= grid[i][j] <= 1000, and 1 <= color <= 1000.

Input and Output

Function shape:

def colorBorder(grid: list[list[int]], row: int, col: int, color: int) -> list[list[int]]:
    ...

Examples

Example 1:

grid = [[1,1],[1,2]], row = 0, col = 0, color = 3

The connected component containing (0,0) is {(0,0),(0,1),(1,0)} (all cells with value 1).

Border cells: all three (they all have a neighbor with value 2 or are on the grid edge). Color them 3.

Answer:

[[3, 3], [3, 2]]

Key Insight

BFS/DFS from (row, col) to find all cells in the connected component.

A cell in the component is a border cell if:

• It is on the edge of the grid, or
• At least one of its 4 neighbors has a different value (not in the component).

Color only the border cells.

Algorithm

1. BFS from (row, col) to find all cells with the same original value in the connected component.
2. For each visited cell, check if it is a border cell.
3. Color border cells with the new color.

Correctness

BFS correctly identifies all reachable cells with the same value.

A cell is a border if any neighbor is outside the grid or has a different original value — these are exactly the cells on the boundary of the component.

Edge Cases

• Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
• Return the failure value when the destination is unreachable.
• Check grid or graph boundaries before reading neighbors.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import deque

class Solution:
    def colorBorder(self, grid: list[list[int]], row: int, col: int, color: int) -> list[list[int]]:
        m, n = len(grid), len(grid[0])
        original = grid[row][col]
        visited = set()
        queue = deque([(row, col)])
        visited.add((row, col))
        border = set()
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while queue:
            r, c = queue.popleft()
            is_border = False
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if not (0 <= nr < m and 0 <= nc < n):
                    is_border = True
                elif grid[nr][nc] != original:
                    is_border = True
                elif (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc))
            if is_border:
                border.add((r, c))

        for r, c in border:
            grid[r][c] = color

        return grid

Testing

def run_tests():
    s = Solution()

    assert s.colorBorder([[1,1],[1,2]], 0, 0, 3) == [[3,3],[3,2]]
    assert s.colorBorder([[1,2,2],[2,3,2]], 0, 1, 3) == [[1,3,3],[2,3,3]]
    assert s.colorBorder([[1,1,1],[1,1,1],[1,1,1]], 1, 1, 2) == [[2,2,2],[2,1,2],[2,2,2]]

    print("all tests passed")

run_tests()