Flood Fill

📋

Problem

Imagine you are using a paint bucket tool in a drawing app that fills a connected area with a new color. How does the app decide which pixels to change?

Given a 2D grid representing an image, a starting pixel (sr, sc), and a new color, replace the color of the starting pixel and all adjacent pixels connected 4-directionally with the same original color with the new color. Return the modified image.

1 ≤ image.length, image[0].length ≤ 500 ≤ sr < image.length0 ≤ sc < image[0].length0 ≤ image[i][j], newColor < 2^16

Edge cases: Starting pixel already has the new color → image unchangedImage with only one pixel → color changes if differentImage where no adjacent pixels share the starting pixel's color → only starting pixel changes

</>

IDE

def floodFill(image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:public int[][] floodFill(int[][] image, int sr, int sc, int newColor)vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor)function floodFill(image, sr, sc, newColor)

def floodFill(image, sr, sc, newColor):
    # Write your solution here
    pass

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        // Write your solution here
        return image;
    }
}

#include <vector>
using namespace std;

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    // Write your solution here
    return image;
}

function floodFill(image, sr, sc, newColor) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Recolored disconnected regions with same colorTraversal does not limit to connected pixels; recolors all pixels with original color regardless of connectivity.✅ Use DFS/BFS starting from (sr, sc) and recolor only pixels reachable via 4-directional moves with original color.

Wrong: Infinite recursion or stack overflowNo early exit when starting pixel color equals newColor; recursion revisits same pixels endlessly.✅ Add early return if original color == newColor before starting DFS/BFS.

Wrong: Only starting pixel recolored when connected region existsTraversal does not continue to neighbors; missing recursive or iterative calls to adjacent pixels.✅ Ensure DFS/BFS visits all 4-directionally connected pixels with original color.

Wrong: Pixels with different colors recoloredNo check for pixel color equality before recoloring neighbors.✅ Check if neighbor pixel color equals original color before recoloring and recursing.

Wrong: No change on single pixel image with different colorBase case for single pixel not handled; pixel color not updated.✅ Update pixel color if different from newColor even if image size is 1x1.

✓

Test Cases

Focus on handling smallest and boundary cases like single pixel images and no-op recoloring.

Think about connected components and ensure your traversal covers all and only connected pixels.

Optimize your solution to run in linear time and avoid stack overflow or repeated work.

t1_01basic

Input{"image":[[1,1,1],[1,1,0],[1,0,1]],"sr":1,"sc":1,"newColor":2}

Expected[[2,2,2],[2,2,0],[2,0,1]]

⏱ Performance - must finish in 2000ms

Starting at pixel (1,1) with color 1, all connected pixels with color 1 are changed to 2.

💡 Consider using DFS or BFS to traverse connected pixels.

💡 Check if the current pixel color matches the original color before changing.

💡 Avoid revisiting pixels by changing color only if it matches original color and is not already newColor.

Why it failed: Failed basic case: likely did not check original color before recoloring or recolored pixels incorrectly. Fix by verifying pixel color matches original color before changing.

✓ Correctly implemented flood fill with proper DFS/BFS and color checks.

t1_02basic

Input{"image":[[0,0,0],[0,1,1]],"sr":1,"sc":1,"newColor":1}

Expected[[0,0,0],[0,1,1]]

⏱ Performance - must finish in 2000ms

Starting pixel (1,1) already has newColor 1, so image remains unchanged.

💡 Check if starting pixel's color is already the newColor before processing.

💡 If original color equals newColor, return image immediately to avoid unnecessary work.

💡 Add an early exit condition to improve efficiency and correctness.

Why it failed: Failed to handle early exit when starting pixel color equals newColor, causing unnecessary changes or infinite recursion. Fix by returning image immediately if original color == newColor.

✓ Proper early exit implemented when starting pixel color equals newColor.

t2_01edge

Input{"image":[[0]],"sr":0,"sc":0,"newColor":1}

Expected[[1]]

⏱ Performance - must finish in 2000ms

Single pixel image with different color; pixel changes to newColor.

💡 Test smallest possible image size: 1x1.

💡 Ensure function handles single element arrays correctly.

💡 Check that pixel color changes if different from newColor.

Why it failed: Failed single pixel case: did not update pixel color correctly or returned original image. Fix by updating pixel color if different from newColor.

✓ Correctly handles single pixel image color change.

t2_02edge

Input{"image":[[1,1,1],[1,1,1],[1,1,1]],"sr":0,"sc":0,"newColor":1}

Expected[[1,1,1],[1,1,1],[1,1,1]]

⏱ Performance - must finish in 2000ms

Starting pixel already has newColor; entire image unchanged.

💡 Check for early exit when original color equals newColor.

💡 Avoid recoloring or infinite recursion in this scenario.

💡 Return image immediately if no changes needed.

Why it failed: Did not handle early exit for starting pixel color == newColor, causing unnecessary processing or stack overflow. Fix by adding early return.

✓ Proper early exit prevents unnecessary processing.

t2_03edge

Input{"image":[[1,2,3],[4,5,6],[7,8,9]],"sr":1,"sc":1,"newColor":10}

Expected[[1,2,3],[4,10,6],[7,8,9]]

⏱ Performance - must finish in 2000ms

Starting pixel color 5 has no adjacent pixels with same color; only starting pixel changes.

💡 Check adjacency only for pixels with same original color.

💡 Do not recolor pixels with different colors.

💡 Ensure only connected region is recolored.

Why it failed: Incorrectly recolored pixels not connected or with different colors. Fix by checking adjacency and color equality before recoloring.

✓ Correctly recolors only connected pixels with original color.

t3_01corner

Input{"image":[[1,1,0,0],[1,0,0,1],[0,0,1,1],[1,1,1,0]],"sr":0,"sc":1,"newColor":3}

Expected[[3,3,0,0],[3,0,0,1],[0,0,1,1],[1,1,1,0]]

⏱ Performance - must finish in 2000ms

Only the connected region of color 1 starting at (0,1) is recolored; disconnected regions remain unchanged.

💡 Flood fill must only recolor connected pixels sharing original color.

💡 Avoid recoloring disconnected regions with same color.

💡 Use DFS/BFS to traverse only connected pixels.

Why it failed: Incorrectly recolored disconnected regions with same color. Fix by limiting traversal to connected pixels only.

✓ Correctly recolors only connected region.

t3_02corner

Input{"image":[[1,1,1],[1,1,1],[1,1,1]],"sr":1,"sc":1,"newColor":2}

Expected[[2,2,2],[2,2,2],[2,2,2]]

⏱ Performance - must finish in 2000ms

Entire image recolored since all pixels connected and same original color.

💡 Ensure recursion or iteration covers all connected pixels.

💡 Avoid missing any pixel in connected region.

💡 Use direction arrays or loops to visit all neighbors.

Why it failed: Missed some connected pixels during traversal. Fix by checking all four directions for each pixel.

✓ All connected pixels correctly recolored.

t3_03corner

Input{"image":[[0,0,0],[0,1,1]],"sr":1,"sc":1,"newColor":2}

Expected[[0,0,0],[0,2,2]]

⏱ Performance - must finish in 2000ms

Only connected pixels with original color 1 starting at (1,1) recolored to 2; pixels with color 0 unchanged.

💡 Do not recolor pixels with different colors than original.

💡 Check color equality before recoloring neighbors.

💡 Use BFS/DFS to traverse only matching color pixels.

Why it failed: Incorrectly recolored pixels with different colors. Fix by verifying color equality before recoloring neighbors.

✓ Correctly recolors only connected pixels with original color.

t4_01performance

Input{"_description":"n=50x50 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=2500 pixels; O(n) DFS/BFS must complete within 2 seconds.

💡 Flood fill runs in O(n) time where n is number of pixels.

💡 Avoid redundant visits by marking visited pixels.

💡 Use iterative BFS or optimized DFS to prevent stack overflow.

Why it failed: TLE due to exponential or repeated visits; fix by marking visited pixels and using O(n) traversal.

✓ Algorithm runs in O(n) time and completes within time limit.

Practice

1. You are given a connected undirected graph where each node contains a value and a list of its neighbors. The task is to create a deep copy of this graph such that the cloned graph has the same structure but no shared nodes with the original. Which algorithmic approach guarantees an optimal solution that handles cycles and multiple components correctly?

easy

A. Use a brute force DFS that recursively clones neighbors without tracking visited nodes.

B. Use BFS or DFS with a hash map to track visited nodes and clone each node exactly once.

C. Use a greedy approach that clones nodes only when their values are unique.

D. Use dynamic programming to store intermediate clone results indexed by node values.

Solution

1. Step 1: Understand the problem constraints

   The graph may contain cycles and multiple components, so naive recursion can cause infinite loops or duplicate clones.

2. Step 2: Identify the correct approach

   Using BFS or DFS with a hash map to track visited nodes ensures each node is cloned once, preventing infinite recursion and preserving graph structure.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracking visited nodes avoids infinite loops and duplicates [OK]

Hint: Track visited nodes to avoid infinite recursion [OK]

Common Mistakes:

• Not tracking visited nodes causes infinite recursion
• Using node values as keys fails with duplicate values

2. Consider the following Python code for checking if a graph is a valid tree. What is the return value when calling valid_tree(4, [[0,1],[1,2],[2,3]])?

easy

A. true

B. false

C. Raises an exception

D. Returns null

Solution

1. Step 1: Check edge count

   Edges count is 3, nodes count is 4, so edges == n-1 condition passes.

2. Step 2: BFS traversal and cycle detection

   Starting from node 0, BFS visits nodes 0,1,2,3 without revisiting any node or detecting cycles. All nodes are visited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph is connected and acyclic, so valid tree [OK]

Hint: Edges must be n-1 and BFS visits all nodes [OK]

Common Mistakes:

• Confusing cycle detection with revisiting parent
• Forgetting to check all nodes visited

3. Suppose the graph edges can be reused multiple times (multi-edges allowed) and self-loops exist. Which modification to the bipartite check algorithm is necessary to correctly handle this variant?

hard

A. Reject any graph with self-loops immediately as non-bipartite

B. Modify Union-Find to union each edge multiple times without changes

C. Use BFS coloring but skip nodes with self-loops to avoid conflicts

D. Ignore self-loops and treat multi-edges as single edges before running BFS or Union-Find

Solution

1. Step 1: Understand the impact of self-loops on bipartiteness

   A self-loop connects a vertex to itself, making it impossible to assign two different colors, so the graph is not bipartite.

2. Step 2: Recognize that multi-edges do not affect bipartiteness if handled properly

   Multi-edges can be treated as single edges; they don't create odd cycles by themselves.

3. Step 3: Conclude that immediate rejection on self-loops is necessary

   Any presence of self-loops means the graph cannot be bipartite, so the algorithm must detect and reject such graphs upfront.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Self-loops break bipartite property immediately [OK]

Hint: Self-loops always break bipartite property [OK]

Common Mistakes:

• Ignoring self-loops
• Trying to color self-looped nodes

4. Suppose the problem is modified so that islands can be connected diagonally as well (8-direction connectivity). Which of the following changes to the DFS approach correctly counts islands under this new rule?

hard

A. Add diagonal neighbors (r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1) to the DFS calls in addition to the four cardinal directions.

B. Keep the DFS calls unchanged but count diagonally adjacent '1's separately after DFS completes.

C. Use BFS instead of DFS without changing neighbor directions, as BFS handles diagonal connectivity automatically.

D. Modify the grid to mark diagonal neighbors as '1' before running the original DFS.

Solution

1. Step 1: Understand the new connectivity rule

   Islands now connect horizontally, vertically, and diagonally, so DFS must explore all 8 neighbors.

2. Step 2: Modify DFS to include diagonal neighbors

   Add recursive DFS calls for (r+1,c+1), (r+1,c-1), (r-1,c+1), and (r-1,c-1) along with the original four directions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only adding diagonal neighbors to DFS ensures correct island counting with 8-direction connectivity [OK]

Hint: Add diagonal neighbors to DFS for 8-direction connectivity [OK]

Common Mistakes:

• Assuming BFS handles diagonals without code change
• Counting diagonals separately after DFS

5. Suppose the problem is modified so that you can only move in 4 directions (up, down, left, right) instead of 8. Which of the following statements about the shortest path algorithm is true?

hard

A. Greedy Best-First Search guarantees shortest path with 4-direction moves

B. Bidirectional BFS still finds the shortest path, but the path length may be longer due to restricted moves

C. DFS with backtracking becomes optimal since fewer directions reduce complexity

D. Dynamic Programming is required to handle the reduced movement directions

Solution

1. Step 1: Understand movement restriction impact

   Reducing to 4 directions limits possible paths, potentially increasing shortest path length.

2. Step 2: Evaluate algorithm suitability

   Bidirectional BFS still finds shortest path efficiently; DFS and greedy do not guarantee shortest path.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bidirectional BFS adapts to movement constraints, still optimal [OK]

Hint: Bidirectional BFS adapts to movement constraints [OK]

Common Mistakes:

• Assuming DFS or greedy become optimal
• Thinking DP is needed for movement changes