Start by checking if the starting pixel already has the target color to avoid unnecessary work. Use DFS or BFS to traverse all connected pixels with the same original color and update them. Carefully handle grid boundaries and revisit prevention to ensure correctness and avoid infinite recursion.
Problem Statement
Given an m x n integer grid representing an image, where image[i][j] is the pixel value, and integers sr, sc, and color, perform a flood fill starting at image[sr][sc]. Change all connected pixels of the same original color to the new color. Connections are only horizontal and vertical.
Return the updated image after performing the flood fill. Ensure you do not change pixels that are not connected to the starting pixel or have a different color.
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]]
From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color. Note the bottom corner is not colored 2, because it is not horizontally or vertically connected to the starting pixel.
Example 2
Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
The starting pixel is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.
Constraints
- m == image.length
- n == image[i].length
- 1 <= m, n <= 50
- 0 <= image[i][j], color < 216
- 0 <= sr < m
- 0 <= sc < n
Solution Approach
Recursive Depth-First Search
Define a recursive DFS function that paints the current pixel if it matches the original color, then calls itself on all four neighbors. Terminate recursion when out of bounds or color differs.
Iterative Breadth-First Search
Use a queue to track pixels to visit. Pop a pixel, paint it, then enqueue valid neighbors with the same original color. This avoids stack overflow on large grids.
Boundary and Revisit Handling
Always check that indices are within the grid and that the pixel has the original color before painting. Optionally, mark visited pixels to prevent redundant operations.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N) |
| Space | O(N) |
Time complexity is O(N) where N is total pixels, as each pixel is visited once. Space complexity is O(N) in worst case due to recursion stack or queue storage.
What Interviewers Usually Probe
- Checks if you recognize that a recursive DFS naturally models connected components in a grid.
- Looks for handling of edge conditions like starting pixel already having target color.
- Wants to see whether BFS alternative is considered for avoiding deep recursion stack.
Common Pitfalls or Variants
Common pitfalls
- Modifying pixels before checking color can paint unintended areas.
- Failing to handle the starting pixel being the same as the target color can cause infinite recursion.
- Ignoring boundary conditions leads to index errors.
Follow-up variants
- Use DFS with diagonal connections to extend flood fill to 8-direction connectivity.
- Perform flood fill on a 3D matrix for volumetric image processing.
- Implement color replacement with constraints, such as only changing pixels within a certain distance.
How GhostInterview Helps
- Provides guided DFS and BFS templates specifically for the Flood Fill pattern.
- Highlights failure modes like revisiting pixels or infinite recursion for immediate correction.
- Offers step-by-step trace visualization so you can see the flood propagation across the grid.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in the Flood Fill problem?
The primary pattern is Array plus Depth-First Search, as you explore all connected pixels recursively or iteratively.
Can I use BFS instead of DFS for Flood Fill?
Yes, BFS is valid and often used to avoid stack overflow in large grids while achieving the same result.
What should I do if the starting pixel already has the target color?
Skip any operation and return the image immediately to prevent unnecessary recursion or queue processing.
Does Flood Fill consider diagonal connections?
By default, only horizontal and vertical connections are considered; diagonals are a variant extension.
What is the time and space complexity of Flood Fill?
Time complexity is O(N) where N is the number of pixels, and space complexity is O(N) due to recursion stack or queue.
Need direct help with Flood Fill instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Flood Fill from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Contain Virus involves using array-based Depth-First Search to contain viral spread by building walls around infected regions.
Open problem page#695 Max Area of IslandFind the largest connected land area in a binary grid using array traversal and depth-first search efficiently.
Open problem page#778 Swim in Rising WaterSolve the problem of swimming through a grid of rising water with a binary search on the valid answer space.
Open problem page