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 once and looks at four neighbours, and pixels outside it are only looked at as neighbours. The stack holds up to m × n pixels when the whole image is one region.

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

Either works in O(m × n) time. The region is the same in any visiting order, so a queue (breadth first) and a stack (depth first) paint the same pixels. Pick whichever is shorter to write, 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 one, painting changes nothing, so neighbours push each other back on the stack forever. Return the image unchanged in that case; it is already the correct answer.

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. All seven 1s link to it through side-sharing 1s, down the left column, along the bottom row and up the right edge, so all become 5. The two 0s keep their color.

Follow-up

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

Solution

Treat pixels as nodes and join two pixels of the starting color when they share a side. The region is the connected piece holding the start, and any search from the start that walks only through that color finds it. Watch for a new color equal to the old one, and a long winding region that overflows recursion.

Recursive depth-first search

Correct, but does not finish on the largest tests

Intuition

paint(r, c) paints a pixel inside the image that still has the old color, then calls itself on the four neighbours. Every pixel of the region is linked to the start by a path of old color pixels, and the calls follow that path. Painting before the calls stops the spread from circling back, since a painted pixel no longer matches. That only works when the colors differ, so return early when they are equal.

The recursion goes as deep as the path it follows. A one pixel wide snake through an 80 × 80 image is about 3,200 pixels long, so the calls nest about 3,200 deep, and a larger image exhausts any call stack.

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 with a stack you own instead of the call stack. Paint a pixel when you push it, not when you pop it. The color check then doubles as the visited check: no pixel enters the stack twice, and you need no separate grid of marks.

Each pixel of the region is pushed once and checks four neighbours, so the time is O(m × n). The stack lives in ordinary memory, so the 3,200 pixel snake is no problem.

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

Reading image[sr][sc] after you paint it. Save the old color first, or every neighbour is compared against the new color.
Counting diagonal neighbours. Pixels that touch only at a corner are not connected.
Checking a neighbour's color before checking that it is inside the image. Test 0 ≤ row < rows and 0 ≤ col < cols first.
Recursing in Python, whose default limit of 1,000 calls stops on the snake above.
Painting every pixel of the old color in the image. Pixels of that color cut off from the start keep their color.

Frequently asked questions3

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 once and looks at four neighbours, and pixels outside it are only looked at as neighbours. The stack holds up to m × n pixels when the whole image is one region.

Should you use BFS or DFS for Flood Fill?

Either works in O(m × n) time. The region is the same in any visiting order, so a queue (breadth first) and a stack (depth first) paint the same pixels. Pick whichever is shorter to write, 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 one, painting changes nothing, so neighbours push each other back on the stack forever. Return the image unchanged in that case; it is already the correct answer.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

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