• m == image.length, n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], color < 2¹⁶
• 0 <= sr < m, 0 <= sc < n
• The fill spreads only up, down, left and right — never diagonally.

This is the paint-bucket tool from any drawing program, and it is the cleanest possible introduction to an idea that runs through a whole family of grid problems: how to visit an entire connected region without visiting anything twice and without missing anything.

Read the rule carefully first, because it has a subtlety. Pixels are repainted if they share the start's color and are reachable from the start through pixels of that color. Both conditions. A pixel of the right color sitting in a different part of the image is not touched. So this is not a search-and-replace over the image — it is a spreading process constrained by connectivity.

The most literal approach walks the whole image and, for each pixel of the original color, asks whether it connects back to the start.

for r, c in all_pixels:
    if image[r][c] == original and connected_to_start(r, c):   # expensive
        image[r][c] = color

The problem is that connected_to_start is not a cheap test — answering it means performing a search, and a search can sweep the entire image. With up to m × n pixels each triggering a search of up to m × n steps, the cost is O((m × n)²).

The waste is easy to see once stated: every pixel in the same region runs its own search over the same territory to rediscover the same fact. They are all connected to each other; establishing that once should be enough for all of them.

Turn it around. Instead of standing on each pixel and asking whether it can reach the start, stand on the start and let it reach outward.

Repaint the starting pixel. Then look at its four neighbours; any that still hold the original color are part of the region, so repaint them and repeat from each. Any neighbour holding a different color is a wall, and any position off the grid is a wall too, so the spread stops there naturally.

Every pixel in the region is reached exactly once, and the boundary conditions of the region are discovered as a by-product rather than tested for. One traversal replaces thousands.

The spread is naturally expressed as a function that calls itself, so it is worth being exact about what that means.

A recursive function solves a task by dealing with one small part itself and delegating the remainder to another copy of itself. For it to finish rather than run forever, two things must hold.

The first is a base case — an input handled immediately with no further calls. Here there are two: a position outside the grid, and a pixel whose color is not the original. Both simply return.

The second is progress: each call must leave strictly less work behind. Here, every call repaints its own pixel before delegating, so the count of pixels still holding the original color drops by one every time. A quantity that decreases by one and can never go below zero must eventually stop.

Then the part that feels like cheating but is not. When the function calls itself on the pixel above, do not try to follow that call in your head. Assume it correctly fills everything reachable upward and returns. The justification is induction: the base cases are correct by inspection, and if each call on a strictly smaller amount of remaining work is correct, then a call that handles its own pixel and delegates the four directions is correct too. Trusting the call is the whole technique — attempting to trace all the branches is what makes recursion feel impossible.

Underneath, each call in progress occupies a stack frame holding its arguments and the line to resume at. Frames stack up as the fill pushes outward and unwind as calls return. That is also the memory cost: the deepest chain of calls, which for a snaking region can be the whole image.

def flood_fill(image, sr, sc, color):
    original = image[sr][sc]
    if original == color:
        return image                      # already done; also prevents infinite recursion
    rows, cols = len(image), len(image[0])

    def fill(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != original:
            return                        # base case: off-image, or a wall
        image[r][c] = color               # repaint BEFORE recursing
        fill(r + 1, c)
        fill(r - 1, c)
        fill(r, c + 1)
        fill(r, c - 1)

    fill(sr, sc)
    return image

Each pixel is entered at most once, since entering it repaints it out of the matching set, and each entry inspects four neighbours. The work is O(m × n) with recursion depth up to O(m × n).

Filling from (1,1) with color 2, where the original color is 1:

1 1 0
1 1 0
0 0 0

Result: the 2×2 block of 1s is entirely 2s and every 0 is untouched. Four pixels repainted, each entered exactly once, and every attempt to re-enter one was stopped by the color check.

Now look at the third example, filling [[0,0,0],[0,0,0]] from (0,0) with color 0. The guard fires on the first line and the image is returned immediately. Delete that guard and this input hangs — which is why it appears in the test set at all.

What has been built here is the fundamental connected-region traversal, and the same seven lines reappear across a whole family of problems with only small substitutions. Three slots vary:

Depth-first search is used here rather than breadth-first for a specific reason worth internalising: the question asks nothing about distance. Every pixel in the region gets the same treatment regardless of how far it sits from the start, so the ordering guarantee that breadth-first search provides is worthless and its queue is pure overhead. When a problem does ask for a shortest path or a minimum number of steps, that calculus flips entirely.

The one real weakness of the recursive form is stack depth. At 50 × 50 it is never a problem, but the identical code on a 300 × 300 grid can nest 90,000 calls and crash. The fix keeps the same logic and swaps the language's call stack for one you manage:

stack = [(sr, sc)]
image[sr][sc] = color
while stack:
    r, c = stack.pop()
    for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
        if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
            image[nr][nc] = color        # mark on discovery, before pushing
            stack.append((nr, nc))

Same visits, same order of exploration, no recursion limit. Note the mark still happens before the push, for exactly the reason it happened before the recursive call.

Train the reflex: when a problem asks you to do something to a whole connected region, do not test each cell for membership. Start at one member and spread, marking as you enter, and let the region's boundary emerge on its own.