Flood Fill

▶

Steps

setup

Initialize variables and check early exit

Store the original color of the starting pixel (1,1) which is 1. Since newColor is 2 and different from original color, proceed with DFS.

💡 Checking if the starting pixel already has the new color avoids unnecessary work.

Line:

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

💡 Early exit prevents infinite recursion or redundant recoloring.

traverse

Start DFS at (1,1), recolor pixel

Begin DFS at pixel (1,1). Change its color from 1 to 2 and mark it as processing.

💡 Recoloring the current pixel prevents revisiting it and marks progress.

Line:

def dfs(r, c):
    image[r][c] = newColor

💡 Changing the pixel color in-place is an efficient way to mark visited nodes.

traverse

Explore neighbor (2,1) of (1,1)

Check neighbor pixel (2,1). It has color 0, which is different from original color 1, so skip DFS on this neighbor.

💡 Only neighbors with the original color are explored to avoid recoloring unrelated pixels.

Line:

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:
        dfs(nr, nc)

💡 Color check prevents DFS from crossing boundaries of the connected region.

traverse

Explore neighbor (0,1) of (1,1)

Check neighbor pixel (0,1). It has color 1, same as original color, so DFS will recurse into (0,1).

💡 DFS moves to neighbors with matching color to continue the fill.

Line:

if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:
    dfs(nr, nc)

💡 DFS expands the connected region by visiting all connected pixels with original color.

traverse

Recolor pixel (0,1)

Change pixel (0,1) color from 1 to 2 to mark it visited and recolored.

💡 Recoloring marks the pixel as processed and prevents revisiting.

Line:

image[r][c] = newColor

💡 In-place recoloring doubles as a visited marker.

traverse

Explore neighbor (0,2) of (0,1)

Check neighbor pixel (0,2). It has color 1, same as original color, so DFS recurses into (0,2).

💡 DFS continues exploring neighbors with matching color.

Line:

if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:
    dfs(nr, nc)

💡 DFS explores all connected pixels in the region.

traverse

Recolor pixel (0,2)

Change pixel (0,2) color from 1 to 2 to mark it visited and recolored.

💡 Recoloring marks progress and prevents revisiting.

Line:

image[r][c] = newColor

💡 In-place recoloring is an efficient visited marker.

traverse

Explore neighbor (1,0) of (0,0)

DFS continues exploring neighbors of previously recolored pixels, eventually recoloring all connected pixels with original color.

💡 DFS explores all connected pixels recursively.

Line:

dfs(nr, nc)

💡 DFS fully explores the connected region.

from typing import List

def floodFill(image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
    original_color = image[sr][sc]  # STEP 1
    if original_color == newColor:  # STEP 1
        return image  # STEP 1
    rows, cols = len(image), len(image[0])  # STEP 2
    directions = [(1,0), (-1,0), (0,1), (0,-1)]  # STEP 2

    def dfs(r, c):  # STEP 2
        image[r][c] = newColor  # STEP 2
        for dr, dc in directions:  # STEP 3
            nr, nc = r + dr, c + dc  # STEP 3
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:  # STEP 3
                dfs(nr, nc)  # STEP 3

    dfs(sr, sc)  # STEP 2
    return image  # STEP 8

📊

Flood Fill - Watch the Algorithm Execute, Step by Step

Watching each recursive call and color change helps you understand how DFS explores connected components in a grid and why early exit prevents unnecessary work.

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Visiting: 1,1

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

1,1

Visiting: 1,1

Edge: 1,1 → 2,1

2,1

Queue / Stack

1,1

Visiting: 0,1

Edge: 1,1 → 0,1

0,1

1,1

Queue / Stack

1,10,1

Visiting: 0,1

0,1

1,1

Queue / Stack

1,10,1

Visiting: 0,2

Edge: 0,1 → 0,2

0,2

0,1

1,1

Queue / Stack

1,10,10,2

Visiting: 0,2

0,2

0,1

1,1

Queue / Stack

1,10,10,2

Visiting: none

0,0

0,1

0,2

1,0

1,1

2,0

1,2

2,1

2,2

Key Takeaways

✓ In-place recoloring serves as both marking visited and changing the pixel color, making the algorithm efficient.

This insight is hard to see from code alone because the color change doubles as a visited marker, avoiding extra memory.

✓ DFS explores all connected pixels with the original color recursively, ensuring the entire connected region is recolored.

Watching the recursion stack and node states visually clarifies how DFS expands and backtracks.

✓ Early exit when the starting pixel already has the new color prevents infinite recursion and redundant work.

This decision is subtle in code but critical to avoid infinite loops when newColor equals original color.

Practice

1. Given the following Python code snippet implementing the BFS approach for Pacific Atlantic Water Flow, and the input heights = [[1,2,2],[3,2,3],[2,4,5]], what is the value of pacific_reachable after initializing the queues and marking the border cells?

easy

A. [[True, True, True], [True, False, False], [True, False, False]]

B. [[True, True, True], [True, False, False], [True, False, True]]

C. [[True, True, True], [False, False, False], [True, False, False]]

D. [[True, False, True], [True, False, False], [True, False, False]]

Solution

1. Step 1: Mark Pacific border cells

   Pacific borders are first row and first column. So pacific_reachable[0][j] and pacific_reachable[i][0] are True.

2. Step 2: Fill pacific_reachable matrix

   For m=3, n=3, first row and first column cells are True, others False initially.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First row and first column are True, rest False [OK]

Hint: Pacific reachable True on top row and left column [OK]

Common Mistakes:

• Forgetting to mark all border cells
• Marking wrong cells True

2. Consider the following code snippet implementing the optimal BFS approach for the Surrounded Regions problem. Given the input board:

board = [
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X']
]

After the BFS marking completes, what is the value of board[3][1]?

easy

A. 'O'

B. 'X'

C. 'S'

D. IndexError (out of bounds)

Solution

1. Step 1: Identify boundary 'O's and mark them

   Only board[3][1] is a boundary 'O', so it is marked 'S' and added to the queue.

2. Step 2: BFS expands from (3,1) marking connected 'O's

   From (3,1), no adjacent 'O's inside the board are connected, so only (3,1) remains 'S'. After BFS, all 'S' revert to 'O'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Boundary 'O' at (3,1) remains 'O' after processing [OK]

Hint: Boundary 'O's remain 'O' after BFS marking [OK]

Common Mistakes:

• Confusing 'S' with final 'O' or 'X' states.
• Forgetting to revert 'S' back to 'O' after BFS.
• Assuming all 'O's get flipped regardless of boundary connection.

3. Examine the following code snippet implementing the Network Delay Time using Bellman-Ford. Which line contains a subtle bug that can cause incorrect results on graphs with unreachable nodes?

medium

A. Line 5: Missing check if dist[u] is infinity before relaxation

B. Line 7: Incorrect comparison operator in relaxation condition

C. Line 10: Breaking early when no updates is incorrect

D. Line 12: Returning -1 instead of max distance is wrong

Solution

1. Step 1: Analyze relaxation condition at line 5

   It lacks a check if dist[u] is infinity, so dist[u] + w can be infinity + w, causing incorrect updates.

2. Step 2: Other lines are correct: early break optimizes, comparison operator is correct, and returning -1 for unreachable nodes is expected

   Thus, the bug is the missing dist[u] != infinity check before relaxation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dist[u] check causes invalid relaxation [OK]

Hint: Always check dist[u] != infinity before relaxing edges [OK]

Common Mistakes:

• Forgetting to check dist[u] before relaxation
• Misunderstanding early break optimization
• Incorrectly handling unreachable nodes

4. Consider the following buggy code snippet from the BFS approach for Pacific Atlantic Water Flow. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line that appends (0, j) to pacific_queue

B. Missing line that sets atlantic_reachable[m-1][j] = True

C. Line that sets pacific_reachable[0][j] = True

D. Line that appends (m-1, j) to atlantic_queue

Solution

1. Step 1: Check border initialization

   Both oceans' reachable arrays must mark all border cells as True initially.

2. Step 2: Identify missing marking

   For atlantic ocean, bottom row cells (m-1, j) are added to queue but not marked reachable, causing BFS to miss them.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing atlantic_reachable[m-1][j] = True causes incomplete results [OK]

Hint: All border cells must be marked reachable initially [OK]

Common Mistakes:

• Forgetting to mark atlantic_reachable bottom row
• Marking visited after BFS causes infinite loops

5. What is the time complexity of the optimal Dijkstra's algorithm variant solution for the minimum effort path problem on an n x m grid?

medium

A. O(n * m^2)

B. O(n * m * log(n * m))

C. O((n * m)^2)

D. O(n * m)

Solution

1. Step 1: Identify graph size

   The grid has n*m nodes and up to 4 edges per node, so edges E = O(n*m).

2. Step 2: Analyze Dijkstra's complexity

   Using a min-heap, each node is pushed/popped at most once, heap operations cost O(log(n*m)), total O(n*m*log(n*m)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Log factor comes from heap operations on n*m nodes [OK]

Hint: Dijkstra on grid -> O(V log V) with V=n*m [OK]

Common Mistakes:

• Confusing edges with nodes count
• Assuming O(n*m^2) due to nested loops
• Ignoring log factor from heap