← Back to problems Solve on LeetCode → See #200 Number of Islands →

Flood Fill

Stack DFS / Recursive — Single Flood from (sr, sc)

LeetCode 733 • Easy • Graphs

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]]
From (sr,sc), replace all same-color cells with newColor. 4-direction flood.

TimeO(R×C)visit each cell once

SpaceO(R×C)stack worst case

Stack: 0 Filled: 0

Processing

In Stack

Filled

Original

Stack

empty

Filled

{ }

Speed:

Ready

Press Play to watch stack-based DFS flood fill from (1,1), or Step to advance one operation at a time.
Replace all same-color cells with newColor. Stack DFS = iterative version of recursion.

✎ Whiteboard

Size: 3

⌨ Type It — Build Muscle Memory

Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.

═══ FLOOD FILL — ITERATIVE (STACK DFS) ═══

PATTERN ▸ Stack DFS O(R×C) · O(R×C)

① EARLY EXIT

if image[sr][sc] == newColor: return image

② INIT

oldColor = image[sr][sc]

stack = [(sr, sc)]

③ DFS LOOP

while stack:

r, c = stack.pop()

if out of bounds or image[r][c]!=oldColor: continue

image[r][c] = newColor

for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:

stack.append((r+dr, c+dc))

═══ FLOOD FILL — RECURSIVE ═══

PATTERN ▸ Recursive DFS O(R×C) · O(R×C)

① BASE & FILL

def dfs(r, c):

if out of bounds or image[r][c]!=oldColor: return

image[r][c] = newColor

② RECURSE 4 DIRECTIONS

for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]: dfs(r+dr, c+dc)

③ CALL

dfs(sr, sc)

▼ your implementation ▼

Verify your solution: