Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 733 Flood Fill - Example and Complexity Analysis

Walkthrough and analysis

Trace image with start (1,1).

Original color at (1,1) is 1. New color is 2.

DFS from (1,1): color is 1, change to 2. Visit neighbors.

  • (0,1): color 1, change to 2. Visit neighbors.
    • (0,0): color 1, change to 2. Neighbors: (0,1) already 2, (1,0) is 1.
    • (0,2): color 1, change to 2. Continue DFS from that cell.
  • (1,0): color 1, change to 2...
  • (2,1): color 0, skip (wrong color).

Result: all connected 1's changed to 2.

Each cell visited once. O(m⋅n)O(m \cdot n) time. Recursion stack: O(m⋅n)O(m \cdot n) worst case.