The problem
Given a map of 1s (land) and 0s (water), return the area of the largest island (the number of land cells in it), or 0.
Input: the 5 × 7 map shown Output: 6
Picture it
Same sea chart as Number of Islands, but now every time we paint an island we also count how many cells we painted. That count is the island’s area. Keep the biggest.
How to recognise it
- The input is a grid of 0s and 1s and cells connect through their four side neighbours.
- You must measure each connected group (its cell count), not only count the groups.
- The answer is a maximum over groups, with 0 when there is no land.
- With up to 50 × 50 cells in LeetCode (and bigger in practice), re-exploring the same group many times is the thing to avoid.
Start with brute force
For every land cell, search its whole island with a fresh visited set and record the island's size. The answer is the largest size seen.
def max_area_brute(grid):
best = 0
for r, c in all_cells(grid):
if grid[r][c] == 1:
seen, st = {(r, c)}, [(r, c)]
while st:
a, b = st.pop()
for x, y in nbrs(grid, a, b):
if grid[x][y] == 1 and (x, y) not in seen:
seen.add((x, y)); st.append((x, y))
best = max(best, len(seen))
return best
An island of k cells is re-measured k times, once from each of its cells. On a grid that is all land, that is R·C searches of R·C cells each, so O((R·C)²) time: for 50 × 50 it is about 6 million steps, but for 300 × 300 it is about 8 × 10^9. Space is O(R·C) for the visited set.
From brute force to the idea
- Find the waste. After measuring an island from one cell you already know the size for all of its cells, yet the brute force measures it again from every other cell.
- Erase as you count. In the shown
flood, each land cell is set to 0 the moment it is queued. The island disappears from the grid as it is measured, so later scans skip it. - Let the flood return its size.
sizestarts at 1 for the first cell, and each newly queued neighbour adds 1. When the queue runs dry,sizeis exactly the island's cell count. - Keep a running maximum. The outer scan calls
floodonly on a1, so each island is measured once.best = max(best, size)keeps the largest. If the grid has no land,beststays 0.
The key idea: measure each island once and delete it, so every cell is processed a single time.
The key idea
Flood fill each island, returning its size. O(rows × cols).
Python solution
def max_area(grid):
best = 0
for r, c in all_cells(grid):
if grid[r][c] == 1:
size = flood(grid, r, c)
best = max(best, size)
return best
def flood(grid, r, c): # paint, count
q, size = deque([(r, c)]), 1
grid[r][c] = 0
while q:
r, c = q.popleft()
for nr, nc in nbrs(grid, r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = 0
size += 1
q.append((nr, nc))
return size
def all_cells(g):
return [(r, c) for r in range(len(g))
for c in range(len(g[0]))]
def nbrs(g, r, c): # in-grid neighbours
R, C = len(g), len(g[0])
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, ncLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O((R·C)²): up to one full search per land cell | O(R·C): a visited set per search |
| Flood fill (shown code) | O(R·C): each cell is queued at most once and has four neighbour checks | O(R·C): the queue, plus the list built by all_cells |
Edge cases
- No land (
[[0,0,0],[0,0,0]]): returns 0. - One land cell (
[[1]]): returns 1. - All land (
[[1,1],[1,1]]): returns 4. - Diagonal contact (
[[1,0],[0,1]]): returns 1, because the two cells are separate islands. - Input is destroyed: all land becomes 0 during the call, so copy the grid first if you need it afterwards.
- Imports:
dequemust be imported. The traversal is iterative, so big islands cause no recursion error.
Common mistakes
- Starting
sizeat 0 insidefloodand so missing the first cell. - Not marking the start cell, so a neighbour counts it a second time.
- Returning the number of islands instead of the largest size, or comparing sizes with
>and forgetting to updatebest. - Marking cells only when popped, which lets one cell be queued many times and inflates the size.
- Using recursive DFS on a large island and hitting the recursion limit.
Return the sizes of all islands as a list, largest first. For [[1,1,0],[0,0,1],[1,0,1]] the answer is [2, 2, 1]. Describe what changes, then write it if you like.
Compare with our answer
flood already returns each island's size, so collect those sizes in a list instead of keeping only the maximum, then sort them.
def island_sizes(grid):
sizes = []
for r, c in all_cells(grid):
if grid[r][c] == 1:
sizes.append(flood(grid, r, c))
return sorted(sizes, reverse=True)
Time O(R·C + k log k) for k islands, and k ≤ R·C, so it is at worst O(R·C log(R·C)). Space O(R·C).
A strong answer mentions: reusing the same flood fill, collecting sizes instead of a maximum, and the extra cost of sorting.
1. A grid holds letters. You must find the size of the largest region of side-by-side cells that all hold the same letter. Which approach fits best?
Counting letters ignores whether cells touch, and a sorted run or a row window cannot follow connections between rows. Flood fill measures each connected region once.
2. What is the time complexity of the shown solution, and why?
The outer scan visits each cell once, and the fills together queue each land cell once. A deque is a plain FIFO queue with O(1) operations, not a sorted structure.
3. A learner deletes the line grid[r][c] = 0 that sits just after q, size = deque([(r, c)]), 1. Which input now returns a wrong area?
The start cell stays 1, so its neighbour finds it, counts it again and queues it. On [[1, 1]] the size becomes 3. In the other inputs the start cell never has a land neighbour, so it is never counted twice.
Score 60% or more and the lesson is marked complete.