# 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

| Item | Meaning |
|---|---|
| Input | Grid, starting cell `(row, col)`, target `color` |
| Output | Grid after coloring the border of the connected component |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
[[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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | BFS visits each cell at most once |
| Space | `O(m * n)` | Visited set and queue |

## 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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---|---|
| 2x2 grid | `[[3,3],[3,2]]` | All component cells are border cells |
| Interior component | Border cells only | Interior cell stays unchanged |
| Full grid | Outer ring colored | Only the border gets colored |