Max Area of Island

▶

Steps

setup

Initialize variables

Set up the grid dimensions, an empty visited set, and max_area initialized to zero before starting traversal.

💡 Initialization prepares the data structures needed to track visited cells and the largest island area found.

Line:

rows, cols = len(grid), len(grid[0])
visited = set()
max_area = 0

💡 We must track visited cells to avoid counting the same land multiple times and keep max_area to record the largest island.

traverse

Start scanning grid at (0,0)

Begin iterating over the grid cells starting at row 0, column 0. The cell is water (0), so no BFS starts here.

💡 We only start BFS when we find unvisited land cells.

Line:

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 1 and (r, c) not in visited:

💡 The algorithm skips water cells and only triggers BFS on unvisited land.

insert

Find first land cell at (0,2), enqueue it

At cell (0,2), land is found and not visited. Enqueue (0,2) to start BFS for this island and initialize area to 0.

💡 Enqueuing the first land cell starts BFS traversal to explore the connected island.

Line:

if grid[r][c] == 1 and (r, c) not in visited:
    queue = deque([(r, c)])
    area = 0

💡 The BFS queue now contains the first cell of a new island to explore.

traverse

Dequeue (0,2), mark visited, increment area

Dequeue cell (0,2) from the queue, mark it visited, and increment the current island area to 1.

💡 Processing a cell means counting it as part of the island and exploring its neighbors.

Line:

row, col = queue.popleft()
if (row, col) in visited:
    continue
visited.add((row, col))
area += 1

💡 Marking visited prevents revisiting the same cell and counting it multiple times.

expand

Check neighbors of (0,2) and enqueue unvisited land

Check neighbors (1,2), (-1,2), (0,3), (0,1). Only (1,2) is valid and land but is water (0), so no enqueue. No neighbors enqueued.

💡 Neighbors are checked to find connected land cells to continue BFS.

Line:

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
        queue.append((nr, nc))

💡 Only valid, unvisited land neighbors are added to the queue to continue BFS.

prune

Finish BFS for island at (0,2), update max_area

Queue is empty, BFS for this island ends. max_area updated to max(0, 1) = 1.

💡 When BFS queue empties, the full island has been counted.

Line:

max_area = max(max_area, area)

💡 max_area tracks the largest island area found so far.

insert

Continue scanning grid, find land at (0,7), enqueue it

At cell (0,7), land found and unvisited. Enqueue (0,7) to start BFS for a new island, reset area to 0.

💡 Each new unvisited land cell triggers a BFS to find a new island.

Line:

if grid[r][c] == 1 and (r, c) not in visited:
    queue = deque([(r, c)])
    area = 0

💡 The BFS queue now contains the first cell of a new island to explore.

traverse

Dequeue (0,7), mark visited, increment area

Dequeue (0,7), mark visited, increment area to 1.

💡 Processing the cell counts it as part of the island.

Line:

row, col = queue.popleft()
if (row, col) in visited:
    continue
visited.add((row, col))
area += 1

💡 Marking visited prevents revisiting and double counting.

expand

Enqueue neighbors of (0,7): (1,7) and (0,8)

Neighbors checked: (1,7) is land and unvisited, enqueue it; (0,8) is water, skip; others invalid or water.

💡 Only valid, unvisited land neighbors are enqueued to continue BFS.

Line:

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
        queue.append((nr, nc))

💡 BFS expands the frontier by adding neighbors to the queue.

traverse

Dequeue (1,7), mark visited, increment area

Dequeue (1,7), mark visited, increment area to 2.

💡 Processing continues to count all connected land cells.

Line:

row, col = queue.popleft()
if (row, col) in visited:
    continue
visited.add((row, col))
area += 1

💡 Each processed cell increases the island area count.

expand

Enqueue neighbors of (1,7): (2,7), (1,8), (1,6)

Neighbors checked: (2,7) water, skip; (1,8) land unvisited, enqueue; (1,6) water, skip; (0,7) visited, skip.

💡 BFS selectively enqueues only valid land neighbors not yet visited.

Line:

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
        queue.append((nr, nc))

💡 BFS frontier grows as new neighbors are discovered.

traverse

Dequeue (1,8), mark visited, increment area

Dequeue (1,8), mark visited, increment area to 3.

💡 Continue counting connected land cells.

Line:

row, col = queue.popleft()
if (row, col) in visited:
    continue
visited.add((row, col))
area += 1

💡 Each visited cell contributes to island area.

expand

Enqueue neighbors of (1,8): (2,8), (1,9), (1,7), (0,8)

Neighbors checked: (2,8) water, skip; (1,9) land unvisited, enqueue; (1,7) visited, skip; (0,8) water, skip.

💡 BFS continues to add new land neighbors to the queue.

Line:

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
        queue.append((nr, nc))

💡 BFS explores neighbors breadth-first, layer by layer.

traverse

Dequeue (1,9), mark visited, increment area

Dequeue (1,9), mark visited, increment area to 4.

💡 Counting continues for the connected island.

Line:

row, col = queue.popleft()
if (row, col) in visited:
    continue
visited.add((row, col))
area += 1

💡 Each visited cell adds to the island area count.

expand

Enqueue neighbors of (1,9): (2,9), (1,10), (1,8), (0,9)

Neighbors checked: (2,9) water, skip; (1,10) water, skip; (1,8) visited, skip; (0,9) water, skip. No new enqueue.

💡 No new land neighbors to add, BFS frontier shrinks.

Line:

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
        queue.append((nr, nc))

💡 BFS ends when no new neighbors are found.

prune

Finish BFS for island at (0,7), update max_area

Queue empty, BFS ends. max_area updated to max(1, 4) = 4.

💡 Update max_area after finishing island traversal.

Line:

max_area = max(max_area, area)

💡 max_area reflects the largest island found so far.

insert

Find next unvisited land at (2,1), enqueue it

At (2,1), land found and unvisited. Enqueue (2,1) to start BFS for a new island, reset area to 0.

💡 Each new island triggers a fresh BFS traversal.

Line:

if grid[r][c] == 1 and (r, c) not in visited:
    queue = deque([(r, c)])
    area = 0

💡 BFS queue now contains a new island's first cell.

traverse

Dequeue (2,1), mark visited, increment area

Dequeue (2,1), mark visited, increment area to 1.

💡 Start counting cells of the new island.

Line:

row, col = queue.popleft()
if (row, col) in visited:
    continue
visited.add((row, col))
area += 1

💡 Each visited cell adds to the island area.

expand

Enqueue neighbors of (2,1): (3,1), (2,2), (1,1), (2,0)

Neighbors checked: (3,1) land unvisited, enqueue; (2,2) land unvisited, enqueue; (1,1) water, skip; (2,0) water, skip.

💡 BFS expands to all connected land neighbors.

Line:

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
        queue.append((nr, nc))

💡 BFS explores all connected land cells to find island size.

prune

Final step: BFS continues until all islands processed, max_area is 6

After processing all islands, max_area is 6, the size of the largest island found.

💡 The algorithm completes after scanning all cells and BFS traversals.

Line:

return max_area

💡 The largest island area is the final answer.

from typing import List
from collections import deque

def maxAreaOfIsland(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])  # STEP 1
    visited = set()  # STEP 1
    max_area = 0  # STEP 1

    for r in range(rows):  # STEP 2
        for c in range(cols):  # STEP 2
            if grid[r][c] == 1 and (r, c) not in visited:  # STEP 3
                queue = deque([(r, c)])  # STEP 3
                area = 0  # STEP 3
                while queue:  # STEP 4
                    row, col = queue.popleft()  # STEP 4
                    if (row, col) in visited:  # STEP 4
                        continue  # STEP 4
                    visited.add((row, col))  # STEP 4
                    area += 1  # STEP 4
                    for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:  # STEP 5
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:  # STEP 5
                            queue.append((nr, nc))  # STEP 5
                max_area = max(max_area, area)  # STEP 6
    return max_area  # STEP 20

📊

Max Area of Island - Watch the Algorithm Execute, Step by Step

Watching the BFS traversal step-by-step reveals how connected components are discovered and counted, which is difficult to grasp from code alone.

Visiting: none

Visiting: 0,0

0,0

Visiting: 0,2

0,2

Queue / Stack

0,2

Visiting: 0,2

0,2

Visiting: none

0,2

Visiting: none

0,2

Visiting: 0,7

0,7

0,2

Queue / Stack

0,7

Visiting: 0,7

0,7

0,2

Visiting: none

Edge: 0,7 → 1,7

0,7

1,7

0,2

Queue / Stack

1,7

Visiting: 1,7

1,7

0,7

0,2

Visiting: none

Edge: 1,7 → 1,8

1,7

1,8

0,7

0,2

Queue / Stack

1,8

Visiting: 1,8

1,8

1,7

0,7

0,2

Visiting: none

Edge: 1,8 → 1,9

1,8

1,9

1,7

0,7

0,2

Queue / Stack

1,9

Visiting: 1,9

1,9

1,8

1,7

0,7

0,2

Visiting: none

1,9

1,8

1,7

0,7

0,2

Visiting: none

0,7

1,7

1,8

1,9

0,2

Visiting: 2,1

2,1

0,7

1,7

1,8

1,9

0,2

Queue / Stack

2,1

Visiting: 2,1

2,1

0,7

1,7

1,8

1,9

0,2

Visiting: none

Edge: 2,1 → 3,1

2,1

3,1

2,2

0,7

1,7

1,8

1,9

0,2

Queue / Stack

3,12,2

Visiting: none

Key Takeaways

✓ BFS explores all connected land cells layer by layer, ensuring each island is fully counted once.

This is hard to see from code alone because the queue and visited set interactions are abstract; visualization shows the frontier clearly.

✓ The visited set prevents revisiting cells, which avoids infinite loops and double counting.

Without visualization, it's easy to miss how revisits are prevented and why they matter.

✓ max_area updates only after BFS completes for each island, reflecting the largest island found so far.

Watching the update timing clarifies when and why max_area changes.

Practice

1. You are given a 2D grid of 0s and 1s. For each cell containing 1, you need to find the distance to the nearest 0. Which algorithmic approach guarantees the shortest distance for all cells efficiently?

easy

A. Use a multi-source Breadth-First Search (BFS) starting from all 0s simultaneously.

B. Run a Depth-First Search (DFS) from each 1 to find the nearest 0.

C. Apply a greedy approach updating distances by scanning rows and columns once.

D. Use a brute force approach checking every cell independently for nearest 0.

Solution

1. Step 1: Understand the problem constraints

   We need shortest distances from each 1 to the nearest 0 in a grid, which is a shortest path problem on an unweighted graph.

2. Step 2: Identify the correct algorithm

   Multi-source BFS starting from all 0s simultaneously guarantees shortest distances because BFS explores neighbors in increasing order of distance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multi-source BFS ensures shortest path in O(m*n) time [OK]

Hint: Shortest path in grid with multiple sources -> multi-source BFS [OK]

Common Mistakes:

• Using DFS which does not guarantee shortest path
• Greedy scanning misses some paths
• Brute force is too slow

2. You are given an undirected graph and need to determine if its vertices can be divided into two groups such that no edge connects vertices within the same group. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Greedy algorithm that assigns groups based on vertex degree

B. Dynamic Programming on subsets of vertices to find valid partitions

C. Depth-First Search (DFS) to find cycles and count their lengths

D. Breadth-First Search (BFS) coloring to assign two colors and check for conflicts

Solution

1. Step 1: Understand the problem as a 2-coloring challenge

   The problem requires checking if the graph is bipartite, which means it can be colored using two colors such that no adjacent vertices share the same color.

2. Step 2: Identify BFS coloring as the optimal approach

   BFS coloring systematically assigns colors level by level and detects conflicts efficiently, guaranteeing correctness and linear time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS coloring is the standard method for bipartite checking [OK]

Hint: BFS coloring detects bipartite conflicts efficiently [OK]

Common Mistakes:

• Assuming greedy degree-based grouping works
• Confusing cycle detection with bipartite check

3. Examine the following buggy flood fill code snippet. Which line contains the subtle bug that can cause infinite recursion or incorrect behavior?

medium

A. Line 6: checking if image[r][c] == newColor before recoloring

B. Line 2: missing check if original_color == newColor before starting

C. Line 8: recoloring pixel before checking neighbors

D. Line 11: boundary check for neighbors

Solution

1. Step 1: Identify missing early exit condition

   The code does not check if the starting pixel's color equals newColor before DFS, which can cause infinite recursion if they are equal.

2. Step 2: Verify other lines

   Line 6's check prevents revisiting recolored pixels, line 8 recolors before neighbors which is correct, and line 11 correctly checks boundaries.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing early exit causes infinite recursion on equal colors [OK]

Hint: Check if start pixel color equals newColor before DFS [OK]

Common Mistakes:

• Forgetting early exit causes infinite recursion
• Misplacing boundary checks

4. What is the time complexity of the optimal BFS approach for the Pacific Atlantic Water Flow problem on an m x n grid, and why?

medium

A. O(m * n) because each cell is enqueued and processed at most once per ocean.

B. O(m * n * log(m * n)) due to priority queue operations in BFS.

C. O(m^2 * n^2) because BFS is run from every cell.

D. O(m + n) because BFS only processes border cells.

Solution

1. Step 1: Analyze BFS visits

   Each BFS starts from border cells and visits each cell at most once per ocean, so total visits ≤ 2 * m * n.

2. Step 2: Confirm no repeated work

   Visited arrays prevent revisiting cells, so BFS complexity is linear in number of cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each cell processed once per ocean -> O(m*n) [OK]

Hint: BFS visits each cell once per ocean [OK]

Common Mistakes:

• Confusing with brute force DFS from every cell
• Assuming BFS uses priority queue

5. Suppose the problem is modified so that land cells can appear or disappear dynamically, and you need to efficiently update the maximum distance after each change. Which approach best supports efficient incremental updates?

hard

A. Use DFS from each water cell to find nearest land after each update.

B. Re-run the multi-source BFS from scratch after each update to recompute distances.

C. Use a dynamic BFS that updates distances only for affected cells using a queue of changed cells.

D. Precompute all distances once and answer queries without updates.

Solution

1. Step 1: Re-running BFS from scratch after each update is too costly for frequent updates.

   DFS is inefficient and does not guarantee shortest paths.

2. Step 2: Dynamic BFS updates distances only for cells affected by land changes, efficiently maintaining correct distances.

   Precomputing once fails to handle updates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incremental BFS updates only affected cells after changes [OK]

Hint: Incremental BFS updates only affected cells after changes [OK]

Common Mistakes:

• Recomputing entire BFS each update
• Using DFS for shortest path
• Ignoring updates after precomputation