Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Easy

Flood Fill

Flood Fill explained: the paint-bucket algorithm as a BFS over same-coloured cells, tested Python code, the same-colour infinite-loop trap and a live visual.

Also searched as: paint bucket fill algorithm · flood fill BFS DFS in a grid

🏝️

Try it live Free

Number of Islands & Grid BFS

In the Grid BFS lab, watch the flood spread from one land cell to all connected land: that spread is exactly a flood fill.

Also useful: Graph Search: BFS vs DFS

Open the playground →

The problem

An image is a 2D grid of colour values. Starting from pixel (sr, sc), recolour it and every pixel connected to it (up, down, left, right) that has the same original colour to a new colour. Return the image.

Inputimage = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output[[2,2,2],[2,2,0],[2,0,1]]

The bottom-right 1 is not connected to the start.

The key insight

This is the paint-bucket tool. The region to repaint is the connected component of cells sharing the start colour, so a BFS or DFS from the start that only steps onto same-coloured neighbours finds it. Recolouring a cell as you visit it doubles as marking it visited.

Brute force first: Repeatedly scanning the whole image and recolouring any cell next to an already-recoloured one works but costs O((m·n)²) in the worst case.

Step-by-step approach

  1. Read the original colour at (sr, sc).
  2. If it already equals the new colour, return the image unchanged (otherwise you loop forever).
  3. Recolour the start and push it on a queue.
  4. Pop a cell; for each in-bounds neighbour with the original colour, recolour it and push it.
  5. When the queue is empty, return the image.

Python solution

PYTHON 3tested
from collections import deque


def flood_fill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:                   # nothing to do, and avoids an endless loop
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    q = deque([(sr, sc)])
    while q:
        r, c = q.popleft()
        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:
                image[nr][nc] = color  # recolouring marks it visited
                q.append((nr, nc))
    return image

Complexity

TimeO(m·n)
SpaceO(m·n)

Each pixel is recoloured and enqueued at most once. In the worst case (whole image one colour) the queue can grow to O(m·n).

Common mistakes

Frequently asked questions

What is the time and space complexity of flood fill?

O(m·n) time for an m by n image since each pixel is processed at most once, and O(m·n) space in the worst case for the queue or recursion stack.

Why check whether the new colour equals the old colour?

If they are equal, recolouring does not change anything, so cells never stop matching the original colour and a DFS or BFS revisits them forever.

Does flood fill use 4 or 8 directions?

This problem uses 4 (up, down, left, right). Paint programs sometimes offer 8-direction fill; only the neighbour list changes.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.