Flood Fill (Recursion)
An easy Recursion interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Recursion
- Sheets
- 1
- Core for
- 11 roles
The problem
Given a 2D grid and a starting cell, fill all connected cells of the same color with a new color, starting from the given cell.
Example 1
- Input
- image = [[3,3,1],[3,1,1],[2,3,3]], sr = 0, sc = 0, newColor = 5
- Output
- [[5,5,1],[5,1,1],[2,3,3]]
- Why
- The three connected 3s in the top-left turn into 5; the 3s at the bottom are not connected to them.
Example 2
- Input
- image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
- Output
- [[2,2,2],[2,2,2]]
Constraints
- 1 <= image.length, image[i].length <= 50
- 0 <= image[i][j], newColor <= 65535
How to think about it
Updated 2026-09-29The grid is an implicit graph where matching adjacent colors define edges. Changing the color of a cell naturally marks it as visited, eliminating the need for an external visited set, as long as the target replacement color is actually different from the start.
Approaches, worst first
Depth-first search recursion
time O(m * n) · space O(m * n)
Record initial color, overwrite current cell with newColor, and recurse into all four orthogonal neighbors matching the initial color. Fits within call stack limits due to small grid bounds.
Breadth-first search queueWrite this one
time O(m * n) · space O(m * n)
Enqueue starting coordinate, then dequeue and recolor neighbors level by level. Prevents deep recursion call stack consumption at the cost of heap allocation.
Where people lose marks · 2
- Infinite recursion when newColor equals the starting cell's original color. Because the cell value never changes, recursion re-visits the same cell indefinitely unless early-exited.
- Checking neighbor validity after recursing rather than before, leading to out-of-bounds matrix indices.
The theory behind it
Recursion — the ground this problem stands on. All Recursion problems
What Recursion is
Recursion is a nesting doll that opens to reveal an identical smaller doll inside. In programming, a function solves a substantial problem by delegating smaller versions of the exact same question to fresh invocations of itself. Each invocation operates on shrunken input until hitting an irreducible foundation called a base case, which returns an immediate answer and permits the waiting cascade to resolve backwards.
When to reach for it
Reach for recursion when a problem possesses self-similar subproblems, such as traversing branched tree structures, exploring graph pathways, or generating combinations. Phrases asking for all permutations, subset generation, exhaustive maze navigation, or hierarchical file system traversals signal recursive decomposition. It is natural whenever the answer to a large instance depends on assembling identical solutions for smaller subsets.
How the pattern works
Structure every recursive method around two mandatory stages: the termination stop and the shrinking recurrence. Write the base condition first so the function exits before attempting further execution. Next, trust the recursive call to return valid answers for smaller inputs without mentally unwinding every level at once. Pass accumulation state forward through parameters, or combine child return values on the ascent phase once deeper calls return.
More Recursion problems
Target Roles
Core requirement for 11 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .