# LeetCode 733: Flood Fill

## Problem Restatement

We are given an image represented as a 2D grid of integers.

Each integer is a pixel color.

We are also given:

```python
sr
sc
color
```

`sr` and `sc` describe the starting pixel:

```python
image[sr][sc]
```

We need to perform a flood fill from that starting pixel.

Flood fill changes the starting pixel and every pixel connected to it with the same original color.

Connection is only 4-directional:

```text
up
down
left
right
```

Diagonal pixels are not connected.

At the end, return the modified image. The official statement defines the image as a 2D integer array and asks us to recolor the starting pixel plus all 4-directionally connected pixels with the same original color.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `image`, `sr`, `sc`, `color` |
| Output | The modified image |
| Starting pixel | `image[sr][sc]` |
| Connected pixels | Adjacent vertically or horizontally |
| Recolored pixels | Only pixels connected to the start with the same original color |

Example function shape:

```python
def floodFill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    ...
```

## Examples

### Example 1

```python
image = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1],
]
sr = 1
sc = 1
color = 2
```

The starting pixel is:

```python
image[1][1] == 1
```

So the original color is `1`.

We recolor all `1` pixels connected to `(1, 1)` through up, down, left, or right moves.

The result is:

```python
[
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1],
]
```

The bottom-right `1` stays unchanged because it is diagonal from a filled region and cannot be reached through 4-directional moves.

### Example 2

```python
image = [
    [0, 0, 0],
    [0, 0, 0],
]
sr = 0
sc = 0
color = 0
```

The original color is already `0`.

The new color is also `0`.

The image does not need to change:

```python
[
    [0, 0, 0],
    [0, 0, 0],
]
```

This case matters because without an early return, DFS may keep revisiting pixels forever.

## First Thought: Traverse the Connected Region

This is a grid connectivity problem.

Each pixel is like a node in a graph.

There is an edge between two pixels if they are adjacent up, down, left, or right.

We need to visit the connected component that starts at `(sr, sc)` and contains only pixels with the same original color.

Depth-first search is a natural fit.

## Key Insight

Save the original color first:

```python
original = image[sr][sc]
```

Then DFS should only enter a cell if:

1. The row is inside the grid.
2. The column is inside the grid.
3. The cell still has the original color.

When a valid cell is found, recolor it immediately.

That recoloring also marks the cell as visited.

So we do not need a separate `visited` set, as long as `original != color`.

## Algorithm

1. Store the original color at the starting pixel.
2. If the original color equals the new color, return `image`.
3. Define a DFS function `dfs(r, c)`.
4. In `dfs`, stop if `(r, c)` is out of bounds.
5. Stop if `image[r][c] != original`.
6. Otherwise, set `image[r][c] = color`.
7. Recursively visit the four neighbors.
8. Return the modified image.

## Correctness

The DFS starts at the given pixel `(sr, sc)`. Since this pixel has the original color, it is part of the region that must be recolored.

Whenever DFS visits a pixel, it first checks that the pixel lies inside the image and has the original color. Therefore, DFS never recolors a pixel outside the image, and it never recolors a pixel with a different color.

After a pixel is recolored, DFS recursively explores its four neighbors. Therefore, any pixel reachable from the start through a path of 4-directionally adjacent original-color pixels will eventually be visited and recolored.

Pixels outside this connected component cannot be reached by such a path, so DFS never recolors them.

Thus the algorithm recolors exactly the required connected component and returns the correct image.

## Complexity

Let `m` be the number of rows and `n` be the number of columns.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | In the worst case, every pixel is visited once |
| Space | `O(m * n)` | The recursion stack can contain many pixels in the worst case |

The image is modified in place.

## Implementation

```python
class Solution:
    def floodFill(
        self,
        image: list[list[int]],
        sr: int,
        sc: int,
        color: int,
    ) -> list[list[int]]:
        rows = len(image)
        cols = len(image[0])
        original = image[sr][sc]

        if original == color:
            return image

        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= rows:
                return

            if c < 0 or c >= cols:
                return

            if image[r][c] != original:
                return

            image[r][c] = color

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        dfs(sr, sc)

        return image
```

## Code Explanation

We first read the grid size:

```python
rows = len(image)
cols = len(image[0])
```

Then we save the starting color:

```python
original = image[sr][sc]
```

This is the only color that may be replaced.

If the new color is the same as the original color, there is no work to do:

```python
if original == color:
    return image
```

This also prevents repeated recursion over already unchanged cells.

The DFS rejects invalid positions:

```python
if r < 0 or r >= rows:
    return

if c < 0 or c >= cols:
    return
```

It also rejects cells that are not part of the original-color component:

```python
if image[r][c] != original:
    return
```

When a cell is valid, we recolor it:

```python
image[r][c] = color
```

Then we visit the four adjacent cells:

```python
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
```

## Testing

```python
def run_tests():
    s = Solution()

    image = [
        [1, 1, 1],
        [1, 1, 0],
        [1, 0, 1],
    ]

    assert s.floodFill(image, 1, 1, 2) == [
        [2, 2, 2],
        [2, 2, 0],
        [2, 0, 1],
    ]

    image = [
        [0, 0, 0],
        [0, 0, 0],
    ]

    assert s.floodFill(image, 0, 0, 0) == [
        [0, 0, 0],
        [0, 0, 0],
    ]

    image = [[1]]
    assert s.floodFill(image, 0, 0, 2) == [[2]]

    image = [
        [1, 0, 1],
        [0, 1, 0],
        [1, 0, 1],
    ]

    assert s.floodFill(image, 1, 1, 2) == [
        [1, 0, 1],
        [0, 2, 0],
        [1, 0, 1],
    ]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard 3 by 3 image | Checks connected component fill |
| New color equals original color | Checks early return |
| Single cell | Minimum image size |
| Diagonal same-color pixels | Confirms diagonals are not connected |