Skip to main content
DSA patterns

Flood Fill

easyGraphsAmazonInfosysTCS

Problem statement

You are given a grid of numbers image, where each number is the colour of one pixel. You are also given a starting pixel (sr, sc) and a new colour color. Repaint the starting pixel and every pixel connected to it that has the same original colour, then return the grid.

"Connected" means you can walk from one pixel to the other using only up, down, left and right steps, staying on pixels of the original colour the whole way. Diagonal steps don't count.

This is the paint-bucket tool from any drawing app. It is also the grid version of a question infra engineers ask all the time: "starting from this one node, what else is reachable?" — for example, which racks in a floor plan are part of the same failed zone.

Examples

Example 1

Input: image = [[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]]

Explanation: The start pixel (1, 1) has colour 1. Every 1 reachable from it by up/down/left/right steps becomes 2. The 1 in the bottom-right corner is only touched diagonally, so it stays 1.

Example 1

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

Output: [[0,0,0],[0,0,0]]

Explanation: The start pixel is already colour 0, the same as the new colour. Nothing needs to change.

Hints

Hint 1: Think of each pixel as a node, with an edge to each of its four neighbours. Which graph walk visits everything reachable from one node?

Approach

Optimal: BFS queue

Intuition

Instead of diving in one direction, spread out in rings, like a drop of ink on paper. Put the start pixel in a queue (a line where the first item in is the first item out). Take a pixel from the front, and add each neighbour that still has the original colour to the back. This is a breadth-first search (BFS).

Paint each pixel as soon as you add it to the queue, not when you take it out. Otherwise two neighbours could both add the same pixel before it gets painted, and it would be processed twice. The same rule as DFS applies: if the new colour equals the original, return straight away.

Steps

  1. Save original = image[sr][sc]. If it equals color, return image.
  2. Paint the start pixel and put it in a queue.
  3. While the queue isn't empty:
    • Take the front pixel (r, c).
    • For each of the four neighbours inside the grid with colour original: paint it, then add it to the queue.
  4. Return image.

Dry run

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

take newly painted and queued queue after
start (1,1) (1,1)
(1,1) (0,1), (1,0) (0,1), (1,0)
(0,1) (0,0), (0,2) (1,0), (0,0), (0,2)
(1,0) (2,0) (0,0), (0,2), (2,0)
(0,0), (0,2), (2,0) none empty

Result: [[2,2,2],[2,2,0],[2,0,1]] — the same as DFS.

Complexity

Time O(m·n) - Each pixel is painted and put in the queue at most once, because we paint it the moment we add it. Each pixel taken from the queue checks four neighbours, which is constant work. So the total is proportional to the number of pixels. This is the same cost as DFS; only the visiting order changes.

Space O(m·n) - The queue holds the pixels waiting to be processed. In the worst case that can be a large part of the grid, so O(m·n). Unlike DFS it uses no recursion, so there is no risk of a stack overflow on big grids. The image is changed in place.

from collections import deque
from typing import List


class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image
        rows, cols = len(image), len(image[0])
        image[sr][sc] = color
        queue = deque([(sr, sc)])
        while queue:
            r, c = queue.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] == original:
                    image[nr][nc] = color
                    queue.append((nr, nc))
        return image


if __name__ == "__main__":
    print(str(Solution().floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)).replace(" ", ""))
    print(str(Solution().floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0)).replace(" ", ""))
RecapThe whole problem in a few lines, for the night before
  • Spot it: recolor a connected region of the same colour, like paint bucket
  • Idea: DFS or BFS from the start cell, recolor each cell and move to its 4 neighbours that still have the original colour
  • Cost: O(m x n) time, O(m x n) space for the stack or queue
  • Trap: if the new colour equals the old colour, return early or the search loops forever

Interview follow-ups

  • Diagonal neighbours also count as connected. What changes?

    Only the list of directions: use eight instead of four, adding (±1, ±1). The walk, the early return and the O(m·n) cost stay the same. Each pixel now checks eight neighbours instead of four, which is still constant work.

  • Count how many separate regions of colour 1 the image has.

    Loop over every pixel. When you find a 1 that isn't visited yet, add one to a counter and flood-fill its whole region (marking it visited). Each pixel is still visited once, so it stays O(m·n). This is the "Number of Islands" problem.

  • The image is huge (a 100,000 × 100,000 map). How do you avoid running out of memory?

    Use BFS rather than recursion, so you can't overflow the call stack. Store the visited marks in a compact bitmap (one bit per pixel) or change the image in place. If the image doesn't fit in memory, split it into tiles, fill each tile, and join regions that touch across tile edges with a union-find.

Frequently asked questions

Every pixel in the region has to be painted, so any correct answer must visit the whole region at least once. DFS and BFS already do exactly that, each pixel once. There is no simpler, slower method worth learning here — the two optimal walks differ only in the order they visit pixels.

The walk uses "this pixel still has the original colour" to mean "not visited yet". If the new colour is the same, painting a pixel doesn't change it. The search would keep stepping back onto pixels it already painted and never stop — an infinite recursion or an endless queue. The early return also skips pointless work, since the answer is the unchanged image.

Both are correct and cost the same. DFS is shorter to write. BFS avoids deep recursion, which matters in Python (its default limit is 1,000 nested calls, which is why the DFS code raises it) and on very large grids in any language. In an interview, write whichever you can explain, and mention the stack-depth trade-off.

Yes, and it's the safer habit for grid problems in general. A separate visited grid works even when you can't change the input or when the new colour equals the old one. It costs O(m·n) extra memory. Here, painting in place is enough and keeps the code shorter.

It's the simplest "find everything connected to this point" problem. The same walk finds every host in a failed network segment, every service affected by an outage (the blast radius), or every resource reachable from one security group. Grids are just an easy way to test that you can write the walk correctly.