Flood Fill

You are given an R × C image where image[i][j] is the pixel's colour, a starting pixel (sr, sc), and a newColor. Perform a flood fill: starting at (sr, sc), repaint that pixel and every pixel 4-directionally connected to it that shares the same original colour with newColor. Return the modified image.

Hints

· Stuck? Reveal one nudge at a time.

Capture the start pixel's original colour before you overwrite it.

Spread 4-directionally to neighbours that equal the original colour, repainting to newColor.

If newColor already equals the original colour, return immediately — otherwise you loop forever.

Common doubts

Recolouring is how you mark visited. If newColor equals the original, repainted cells look unvisited, so the traversal never terminates.

Both O(R·C) and identical output; BFS avoids stack overflow on a large single-colour region.

Same flood-fill core; islands counts regions, flood fill recolours one region from a given start.

Interview follow-ups

· What an interviewer asks next.

Add the four diagonal directions to the neighbour set.

Same algorithm; often with a colour tolerance instead of exact match.

Fun facts

LeetCode 733 — the literal paint-bucket algorithm.
The equal-colour short-circuit is the single most common bug in flood fill.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
The connected block of 1s containing (1,1) is repainted to 2.

Example 2

Input: image = [[7]], sr = 0, sc = 0, newColor = 7
Output: [[7]]
newColor equals the start colour, so the image is unchanged.

Constraints

- 1 <= R, C <= 50 - 0 <= image[i][j], newColor <= 65535 - 0 <= sr < R - 0 <= sc < C

Flood fill is the "paint bucket" tool: from the start pixel, spread to every orthogonally-adjacent pixel of the same starting colour, recolouring as you go. It's a grid traversal (DFS or BFS) with two guards:

Remember the original colour before you overwrite the start — the spread condition compares against it.
If newColor already equals the original, return immediately; otherwise a DFS/BFS that recolours to the same value never marks progress and loops forever.

Every reachable same-colour pixel is visited once, so it's O(R·C).

Prerequisites

Before you start

· Concepts used directly in the solution.

Grid traversal. 4-directional DFS/BFS over pixels.

Match the source colour. only spread to pixels equal to the start's original colour.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What if newColor equals the start colour?”

Return the image unchanged — and guard against the infinite loop.

“Diagonal spread?”

No, 4-directional only.

The ideal opening — say it like this

I record the start colour, then DFS/BFS to every adjacent pixel of that colour, repainting to newColor.

I short-circuit when newColor already equals the start colour to avoid an infinite loop.

Understand the problem

Worked example — image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, newColor=2

start colour = 1; repaint the connected 1-block containing (1,1)
result = [[2,2,2],[2,2,0],[2,0,1]]

Key observations

1Aha

Compare against the original colour

Capture it before overwriting the start pixel.

2Aha

Short-circuit equal colours

newColor == old must return early to avoid an infinite fill.

3Aha

O(R·C)

Each same-colour reachable pixel is repainted once.

Brute force vs optimal

	DFS	BFS
Container	recursion	queue
Time	O(R·C)	O(R·C)
Risk	deep recursion on a big region	none

Both repaint identically; BFS avoids deep recursion. Full code is in the Approaches selector below.

Summary

Key takeaway

Record the start colour, then DFS/BFS to all same-colour 4-connected pixels, repainting to newColor. Return early if newColor equals the original. O(R·C).

old = image[sr][sc]
if old == newColor: return image
flood from (sr,sc): repaint cells equal to old