Number of Islands

▶

Steps

setup

Initialize variables and prepare grid nodes

The algorithm initializes the island count to zero and prepares to iterate over the grid cells. Each cell is represented as a node with its coordinates and initial state 'unvisited'.

💡 Setting up the grid as nodes with states helps visualize which cells have been processed or are pending.

Line:

count = 0
rows, cols = len(grid), len(grid[0])

💡 The grid is ready for traversal, and the island count starts at zero.

traverse

Scan cell (0,0) - land found, start DFS

The algorithm examines cell (0,0), which is land ('1'). It decides to start a DFS from this cell to mark the entire island.

💡 Identifying a land cell triggers the DFS to explore all connected land cells.

Line:

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == '1':

💡 The first island is detected at (0,0), and DFS will mark all connected land cells.

expand

Mark cell (0,0) as visited

DFS marks cell (0,0) as visited by changing its value to '0' to avoid revisiting. The node state changes to 'done'.

💡 Marking visited cells prevents infinite loops and double counting islands.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 The cell (0,0) is now considered water to indicate it has been processed.

expand

DFS explores neighbor (1,0)

DFS moves to neighbor cell (1,0), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS explores all connected land neighbors recursively to mark the entire island.

Line:

dfs(r+1, c)

💡 DFS is expanding to connected land cells to mark the island fully.

expand

Mark cell (1,0) as visited

DFS marks cell (1,0) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells ensures no repeated processing.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (1,0) is now processed and won't be revisited.

expand

DFS explores neighbor (2,0)

DFS moves down to cell (2,0), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS continues exploring connected land cells to cover the entire island.

Line:

dfs(r+1, c)

💡 DFS is systematically exploring all connected land neighbors.

expand

Mark cell (2,0) as visited

DFS marks cell (2,0) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells ensures no repeated processing.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (2,0) is now processed and excluded from future DFS calls.

expand

DFS explores neighbor (2,1)

DFS moves right to cell (2,1), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS explores all four directions to find connected land cells.

Line:

dfs(r, c+1)

💡 DFS is expanding horizontally to cover the island.

expand

Mark cell (2,1) as visited

DFS marks cell (2,1) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells prevents revisiting and completes part of the island.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (2,1) is now processed and excluded from future DFS calls.

expand

DFS explores neighbor (1,1)

DFS moves up to cell (1,1), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS explores all neighbors to ensure the entire island is marked.

Line:

dfs(r-1, c)

💡 DFS is exploring upward neighbors to cover the island fully.

expand

Mark cell (1,1) as visited

DFS marks cell (1,1) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells prevents revisiting and completes part of the island.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (1,1) is now processed and excluded from future DFS calls.

expand

DFS explores neighbor (0,1)

DFS moves up to cell (0,1), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS continues exploring connected land neighbors.

Line:

dfs(r-1, c)

💡 DFS is expanding upward to cover the island fully.

expand

Mark cell (0,1) as visited

DFS marks cell (0,1) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells prevents revisiting and completes part of the island.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (0,1) is now processed and excluded from future DFS calls.

expand

DFS explores neighbor (0,2)

DFS moves right to cell (0,2), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS explores all connected land neighbors to cover the island.

Line:

dfs(r, c+1)

💡 DFS is expanding rightward to cover the island fully.

expand

Mark cell (0,2) as visited

DFS marks cell (0,2) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells prevents revisiting and completes part of the island.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (0,2) is now processed and excluded from future DFS calls.

expand

DFS explores neighbor (0,3)

DFS moves right to cell (0,3), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS continues exploring connected land neighbors to cover the island.

Line:

dfs(r, c+1)

💡 DFS is expanding rightward to cover the island fully.

expand

Mark cell (0,3) as visited

DFS marks cell (0,3) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells prevents revisiting and completes part of the island.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (0,3) is now processed and excluded from future DFS calls.

expand

DFS explores neighbor (1,3)

DFS moves down to cell (1,3), which is land ('1'). It is pushed onto the stack and marked 'processing'.

💡 DFS explores all connected land neighbors to cover the island.

Line:

dfs(r+1, c)

💡 DFS is expanding downward to cover the island fully.

expand

Mark cell (1,3) as visited

DFS marks cell (1,3) as visited by setting its value to '0' and changes its state to 'done'.

💡 Marking visited cells prevents revisiting and completes part of the island.

Line:

grid[r][c] = '0'  # mark visited by sinking island

💡 Cell (1,3) is now processed and excluded from future DFS calls.

prune

DFS complete, increment island count

DFS completes marking all connected land cells of the first island. The island count is incremented to 1. The algorithm resumes scanning the grid for other islands.

💡 Incrementing the island count after DFS ensures each island is counted exactly once.

Line:

count += 1

💡 One island has been fully processed and counted.

from typing import List

def numIslands(grid: List[List[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        # STEP 3,5,7,... Mark current cell visited
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark visited by sinking island
        dfs(r+1, c)  # STEP 4,6,8,... explore down
        dfs(r-1, c)  # explore up
        dfs(r, c+1)  # explore right
        dfs(r, c-1)  # explore left

    count = 0
    for r in range(rows):
        for c in range(cols):
            # STEP 2: check each cell
            if grid[r][c] == '1':
                dfs(r, c)  # STEP 2: start DFS
                count += 1  # STEP 20: increment count
    return count

📊

Number of Islands - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization helps you understand how DFS explores connected components in a grid and how marking visited cells prevents counting the same island multiple times.

Visiting: none

0,0

0,1

0,2

0,3

0,4

1,0

1,1

1,2

1,3

1,4

2,0

2,1

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

Visiting: 0,0

0,0

0,1

1,0

Queue / Stack

0,0

Visiting: 0,0

0,0

0,1

1,0

Queue / Stack

0,0

Visiting: 1,0

Edge: 0,0 → 1,0

1,0

0,0

0,1

Queue / Stack

0,01,0

Visiting: 1,0

1,0

0,0

0,1

Queue / Stack

0,01,0

Visiting: 2,0

Edge: 1,0 → 2,0

2,0

1,0

0,0

Queue / Stack

0,01,02,0

Visiting: 2,0

2,0

1,0

0,0

Queue / Stack

0,01,02,0

Visiting: 2,1

Edge: 2,0 → 2,1

2,1

2,0

1,0

Queue / Stack

0,01,02,02,1

Visiting: 2,1

2,1

2,0

1,0

Queue / Stack

0,01,02,02,1

Visiting: 1,1

Edge: 2,1 → 1,1

1,1

2,1

2,0

Queue / Stack

0,01,02,02,11,1

Visiting: 1,1

1,1

2,1

2,0

Queue / Stack

0,01,02,02,11,1

Visiting: 0,1

Edge: 1,1 → 0,1

0,1

1,1

2,1

Queue / Stack

0,01,02,02,11,10,1

Visiting: 0,1

0,1

1,1

2,1

Queue / Stack

0,01,02,02,11,10,1

Visiting: 0,2

Edge: 0,1 → 0,2

0,2

0,1

1,1

Queue / Stack

0,01,02,02,11,10,10,2

Visiting: 0,2

0,2

0,1

1,1

Queue / Stack

0,01,02,02,11,10,10,2

Visiting: 0,3

Edge: 0,2 → 0,3

0,3

0,2

0,1

Queue / Stack

0,01,02,02,11,10,10,20,3

Visiting: 0,3

0,3

0,2

0,1

Queue / Stack

0,01,02,02,11,10,10,20,3

Visiting: 1,3

Edge: 0,3 → 1,3

1,3

0,3

0,2

Queue / Stack

0,01,02,02,11,10,10,20,31,3

Visiting: 1,3

1,3

0,3

0,2

Queue / Stack

0,01,02,02,11,10,10,20,31,3

Visiting: none

0,0

0,1

0,2

0,3

1,0

1,1

1,3

2,0

2,1

0,4

1,2

1,4

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

Key Takeaways

✓ DFS marks all connected land cells of an island by recursively visiting neighbors and marking them visited.

This insight is hard to see from code alone because the recursion and marking happen implicitly; visualization shows explicit traversal and marking.

✓ Marking visited cells by changing '1' to '0' prevents revisiting and double counting islands.

Understanding this in-place modification is easier when watching the grid update step-by-step.

✓ The island count increments only after a full DFS completes, ensuring each island is counted exactly once.

Seeing the count increment after DFS clarifies why partial exploration doesn't increase the count.

Practice

1. Examine the following buggy code snippet for the optimal BFS approach. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line that sets dist[nr][nc] = dist[r][c] + 1 without checking if dist[nr][nc] == -1

B. Line that initializes dist[r][c] = 0 for land cells

C. Line that appends initial land cells to the queue

D. Line that returns -1 if all cells are land or water

Solution

1. Step 1: Identify that updating dist[nr][nc] without checking if it was visited causes overwriting distances.

   This leads to revisiting cells multiple times, causing infinite loops or incorrect distances.

2. Step 2: The missing condition dist[nr][nc] == -1 before updating and enqueueing is the bug.

   Without it, BFS does not behave correctly as a shortest path search.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited check prevents infinite loops and ensures correct distances [OK]

Hint: Always check if neighbor is unvisited before updating distance [OK]

Common Mistakes:

• Forgetting visited check causes infinite loops
• Misplacing initialization lines
• Incorrect early return conditions

2. Examine the following modified Union-Find based bipartite check code. Which line contains a subtle bug that can cause incorrect results on disconnected graphs?

medium

A. Line: for node in range(n):

B. Line: for i in range(1, len(graph[node])):

C. Line: if not uf.union(graph[node][0], graph[node][i]):

D. Line: return True

Solution

1. Step 1: Identify missing iteration over disconnected components

   The loop iterates over all nodes, but the union-find approach requires checking all connected components separately to detect conflicts.

2. Step 2: Recognize that skipping isolated components causes missed conflicts

   If the graph has disconnected parts, conflicts in unvisited components won't be detected, causing false positives.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Iterating over all nodes is necessary but must include component checks [OK]

Hint: Missing component checks cause false bipartite positives [OK]

Common Mistakes:

• Assuming single pass covers all components
• Ignoring isolated nodes

3. What is the worst-case time complexity of the DFS-based solution for the Rotting Oranges problem on an m x n grid, considering pruning and recursive calls?

medium

A. O(m * n * 4) due to each cell visited once with up to 4 neighbors

B. O(m * n * m * n) because each cell can be revisited multiple times

C. O(m * n) ignoring recursion stack and repeated visits

D. O(m * n * T) where T is the number of minutes until no change

Solution

1. Step 1: Identify number of cells and neighbors

   Grid has m*n cells; each cell has up to 4 neighbors to explore.

2. Step 2: Consider pruning and repeated visits

   Pruning ensures each cell is visited at most once per time update, bounding calls to O(m*n*4).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS with pruning limits repeated visits, so complexity is O(m*n*4) [OK]

Hint: Pruning limits DFS calls to constant neighbors per cell [OK]

Common Mistakes:

• Assuming exponential revisits
• Confusing time steps with grid size
• Ignoring recursion stack space

4. Suppose the problem changes: now flights can be reused multiple times (cycles allowed), but you still want the cheapest price within K stops. Which modification to the algorithm is necessary to handle this correctly? A) Use Bellman-Ford with K+1 iterations to relax edges repeatedly. B) Use the same Dijkstra approach without changes since it handles cycles. C) Use DFS with memoization to avoid infinite loops. D) Use BFS without tracking stops because cycles are allowed.

hard

A. Use Bellman-Ford with K+1 iterations to relax edges repeatedly.

B. Use the same Dijkstra approach without changes since it handles cycles.

C. Use DFS with memoization to avoid infinite loops.

D. Use BFS without tracking stops because cycles are allowed.

Solution

1. Step 1: Understand reuse and cycles

   Allowing reuse means cycles can exist, so Dijkstra's assumption of no negative cycles and no repeated nodes fails.

2. Step 2: Identify suitable algorithm

   Bellman-Ford can handle cycles by relaxing edges up to K+1 times, correctly computing shortest paths with stop constraints.

3. Step 3: Why other options fail

   Dijkstra without changes may loop infinitely or miss valid paths; DFS risks stack overflow; BFS without stops tracking ignores constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bellman-Ford handles cycles with controlled relaxations [OK]

Hint: Bellman-Ford handles cycles with limited relaxations [OK]

Common Mistakes:

• Assuming Dijkstra works with cycles
• Ignoring stops tracking in BFS
• Using DFS without pruning leads to infinite recursion

5. Suppose the problem changes: fresh oranges can become rotten multiple times, and rot can spread back to previously rotten oranges if it results in a faster rot time. Which modification to the DFS-based solution correctly handles this scenario?

hard

A. Switch to a brute force simulation updating the grid minute by minute until no changes

B. Keep the original DFS with pruning but run it multiple times until no updates occur

C. Use a multi-source BFS but do not track times, just mark visited once

D. Remove the pruning condition that skips DFS if time_grid[r][c] <= time, allowing revisits with better times

Solution

1. Step 1: Understand new rot dynamics

   Rot can improve previously recorded rot times, so pruning based on time_grid[r][c] <= time is invalid.

2. Step 2: Modify DFS to allow revisits with better times

   Removing pruning condition enables DFS to update time_grid when a faster rot path is found.

3. Step 3: Confirm correctness

   This ensures all cells have minimum rot times even if rot spreads back to previously rotten oranges.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Allowing revisits with better times handles dynamic rot spread correctly [OK]

Hint: Allow revisits if they improve rot time [OK]

Common Mistakes:

• Keeping pruning causes stale times
• Using BFS without time tracking
• Brute force is inefficient