progress

~/problems / Graphs / DFS and connected components

Max Area of Island

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~20 min Snapchat

Implement max_area_of_island(grid) -> int.

grid is a list of rows of integers, 1 for land and 0 for water. Land cells that touch up, down, left or right belong to the same island, and an island's area is its number of cells. Return the largest area, or 0 if there's no land at all.

max_area_of_island([
    [1, 1, 0, 0, 1],
    [0, 1, 0, 1, 1],
    [0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0],
])
# 4   (the island on the right: (0,4), (1,3), (1,4), (2,4))

Grids go up to 300×300. You may modify grid.

⭐ Bonus: a speed test on an all-land 300×300 grid earns a star in O(rows·cols) without deep recursion (Python's default limit is about 1,000 frames).

Show hint

Starting from any land cell you haven't seen, you can visit its whole island, counting cells as you go, and mark them so they're never counted again.

Topic: DFS and connected components. Iterative DFS / flood fill; count and label components.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc