LeetCode 695 · Graphs

Max Area of Island, explained with a picture

Measuring the biggest island.

MediumGraphs
▶ Watch it step by step

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

  1. 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.
  2. 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.
  3. Let the flood return its size. size starts at 1 for the first cell, and each newly queued neighbour adds 1. When the queue runs dry, size is exactly the island's cell count.
  4. Keep a running maximum. The outer scan calls flood only on a 1, so each island is measured once. best = max(best, size) keeps the largest. If the grid has no land, best stays 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, nc

LeetCode 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

ApproachTimeSpace
Brute forceO((R·C)²): up to one full search per land cellO(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 checksO(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: deque must be imported. The traversal is iterative, so big islands cause no recursion error.

Common mistakes

  • Starting size at 0 inside flood and 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 update best.
  • 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.
Your turn: every island size

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.

Check what stuck

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?

2. What is the time complexity of the shown solution, and why?

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?

Score 60% or more and the lesson is marked complete.