Flood Fill

Q: What is the time complexity of Flood Fill?

O(m × n) for an image with m rows and n columns. Each pixel of the region is pushed on the stack once and looks at four neighbours, and pixels outside the region are only looked at as neighbours. The stack can hold up to m × n pixels when the whole image is one region.

Q: Should you use BFS or DFS for Flood Fill?

Either works and both take O(m × n) time. The region is the same whatever order you visit it in, so a queue (breadth first) and a stack (depth first) paint the same pixels. Pick whichever is shorter to write in your language, and avoid recursion on large images.

Q: Why does Flood Fill loop forever when the new color is the same as the old one?

The usual solution treats "still has the old color" as "not visited yet". When the new color equals the old color, painting a pixel does not change it, so its neighbours push it back on the stack and the search never ends. Checking for this case first and returning the image fixes it, and the unchanged image is the correct answer.

Q: Can Flood Fill be solved recursively?

Yes, a function that paints a pixel and calls itself on each neighbour of the old color is correct. The risk is depth: the recursion goes as deep as the longest path the search follows, which on a winding region can be thousands of calls. An explicit stack does the same work without that limit.

EasyGraphs

+10

An image is a grid of whole numbers, where each number is the color of one pixel. You get the image as a list of rows, a starting pixel at row sr and column sc, and a new color. Repaint the region that holds the starting pixel: every pixel of the starting pixel's color that you can reach from it by stepping up, down, left or right through pixels of that same color. Return the image after the repaint.

Function

floodFill(image: integer-2d-array, sr: integer, sc: integer, color: integer) → integer-2d-array

imageinteger-2d-array: the image as a list of rows, one number per pixel
srinteger: the row of the starting pixel, counted from 0
scinteger: the column of the starting pixel, counted from 0
colorinteger: the new color for the region
Returnsinteger-2d-array: the image after the region is repainted

Constraints

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Every row has the same length.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length and 0 ≤ sc < image[0].length

Examples

Input: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Output: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Explanation: The start holds color 1. The 1 to its right, the 1s down the left column and along the bottom row, and the 1 above the bottom right corner all link to it, so all seven become 5. The two 0s are a different color and keep it.

+18 hidden tests on Submit

Follow-up

How would your solution change if pixels that touch only at a corner also counted as connected?

Solution

The region is a connected piece of a graph: pixels are nodes, and two pixels of the starting color that share a side are joined. Any search that starts at the given pixel and walks only through that color finds the whole region. The two traps are an image where the new color equals the old one, and a long winding region that breaks a recursive search.

Recursive depth-first search

Correct, but does not finish on the largest tests

Intuition

Write a function paint(r, c) that does one small thing: if (r, c) is inside the image and still has the old color, give it the new color and call itself on the four neighbours. One call on the starting pixel spreads through the whole region, because every pixel of the region is linked to the start by a path of old color pixels, and the calls follow that path.

Painting the pixel before the four calls is what stops the spread from going in circles: when a neighbour calls back into a painted pixel, the color no longer matches and the call returns at once. That only works when the new color differs from the old one, so check that first and return the image unchanged when they are equal.

The work is O(m × n), but the call stack is the weak spot. The recursion goes as deep as the path it is following. A one pixel wide snake through an 80 × 80 image is about 3,200 pixels long, so the calls nest about 3,200 deep. Python stops at 1,000 by default and raises an error, which is why this approach does not finish on the largest tests. Other languages allow deeper calls, but a larger image would exhaust their call stack too.

Algorithm

Read old = image[sr][sc]. If old equals color, return the image.
Define paint(r, c): return if (r, c) is outside the image or its color is not old.
Otherwise set image[r][c] = color and call paint on the pixels above, below, left and right.
Call paint(sr, sc) and return the image.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])

    def paint(r, c):
        # Stop outside the image and at any pixel that is not the old color.
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = color
        paint(r + 1, c)
        paint(r - 1, c)
        paint(r, c + 1)
        paint(r, c - 1)

    paint(sr, sc)
    return image

Depth-first search with an explicit stack

Intuition

Do the same walk, but keep the pixels still to visit on a stack you own instead of on the call stack. Paint the starting pixel and push it. Pop a pixel, look at its four neighbours, and for each neighbour inside the image that still has the old color, paint it and push it. When the stack is empty, you have painted the whole region.

Paint a pixel when you push it, not when you pop it. A painted pixel no longer has the old color, so the color check doubles as the visited check: no pixel enters the stack twice, and you need no separate grid of marks. As in the recursive version, this needs the new color to differ from the old one, so return the image unchanged when they are equal.

Each pixel of the region is pushed once and checks four neighbours, so the time is O(m × n). The stack holds at most the region's pixels. It lives in ordinary memory, so a winding region of 3,200 pixels is no problem, where the recursive version ran out of call stack.

Algorithm

Read old = image[sr][sc]. If old equals color, return the image.
Paint (sr, sc) and push it on a stack.
Pop a pixel and look at its four neighbours.
For each neighbour inside the image whose color is old, paint it and push it.
When the stack is empty, return the image.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    # Painting a region its own color changes nothing. Returning here also
    # stops the search from pushing the same cells forever.
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    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] == old:
                # Paint on push: a painted cell no longer matches old,
                # so it can never be pushed twice.
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

Pitfalls and edge cases

Most wrong answers come from the same color case, from leaving the image, or from recursion on a long region.

Forgetting the case where color equals the starting color. Painting then changes nothing, so a search that uses the color as its visited mark pushes the same pixels forever.
Reading image[sr][sc] after you paint it. Save the old color first, or you will compare every neighbour against the new color.
Counting diagonal neighbours. Pixels that touch only at a corner are not connected.
Checking a neighbour's color before checking it is inside the image. Test 0 ≤ row < rows and 0 ≤ col < cols first.
Recursion on a large image. A one pixel wide path through an 80 × 80 image is about 3,200 pixels long, deep enough to pass Python's recursion limit.
Painting every pixel of the old color in the whole image. Pixels of that color that are cut off from the start must keep their color.

Frequently asked questions4

What is the time complexity of Flood Fill?

O(m × n) for an image with m rows and n columns. Each pixel of the region is pushed on the stack once and looks at four neighbours, and pixels outside the region are only looked at as neighbours. The stack can hold up to m × n pixels when the whole image is one region.

Should you use BFS or DFS for Flood Fill?

Either works and both take O(m × n) time. The region is the same whatever order you visit it in, so a queue (breadth first) and a stack (depth first) paint the same pixels. Pick whichever is shorter to write in your language, and avoid recursion on large images.

Why does Flood Fill loop forever when the new color is the same as the old one?

The usual solution treats "still has the old color" as "not visited yet". When the new color equals the old color, painting a pixel does not change it, so its neighbours push it back on the stack and the search never ends. Checking for this case first and returning the image fixes it, and the unchanged image is the correct answer.

Can Flood Fill be solved recursively?

Yes, a function that paints a pixel and calls itself on each neighbour of the old color is correct. The risk is depth: the recursion goes as deep as the longest path the search follows, which on a winding region can be thousands of calls. An explicit stack does the same work without that limit.

Python

def floodFill(image, sr, sc, color):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
sr = 0
sc = 0
color = 5

Expected

[[5, 5, 0], [5, 0, 5], [5, 5, 5]]