Max Area of Island — InterviewPrepKit

Solving tips

See the grid as a graph: each land cell links to its 4 orthogonal land neighbors and an island is a connected component; you want the largest component's size.
Scan every cell; on an unvisited 1, flood-fill (DFS/BFS) the whole island returning its cell count, and track the running max; O(m*n) time.
Mark cells visited by sinking them to 0 for O(1) extra space, or use a separate visited set if the input must stay intact.
Pitfall: connectivity is 4-directional only (no diagonals), and initialize best=0 so all-water returns 0 naturally.

Problem

You’re given an m × n binary grid where 1 is land and 0 is water. An island is a maximal group of 1-cells connected 4-directionally (up, down, left, right — not diagonally). The area of an island is its number of cells.

Return the area of the largest island. If there is no land at all, return 0.

Examples

grid = [[1,1,0],[1,0,0],[0,0,1]] → 3 — the top-left island has 3 cells; the lone cell bottom-right has area 1.
grid = [[0,0,0],[0,0,0]] → 0 — all water.
grid = [[1,1,1],[1,1,1]] → 6 — one island covering the whole grid.

Constraints

m == len(grid), n == len(grid[0]), 1 <= m, n <= 50.
Each cell is 0 or 1.

Think about it first

Hint 1

Think of the grid as a graph: each land cell is a node, with edges to its 4 orthogonal land neighbors. An island is a connected component; you want the size of the largest one.

Hint 2

Scan every cell. When you hit an unvisited 1, launch a DFS/BFS that floods the whole island, counting cells, and mark them visited so you never recount. Track the running maximum count.

Hint 3

"Visited" can be a separate set, or you can sink land as you go by writing 0 over each counted cell (destructive but O(1) extra space). Union-find is an alternative: union adjacent land cells and take the largest set size.

TL;DR

Flood-fill each island and track the largest — DFS or BFS over the grid graph, O(m·n) time; union-find is an equivalent alternative.

Approach 1 — DFS flood fill

The insight: a grid is an implicit graph — each land cell links to its 4 orthogonal land neighbors, and an island is a connected component. Scan every cell; on an unvisited 1, DFS floods the entire component, returning its cell count. Mark cells visited (here by sinking them to 0) so each is counted once. Keep the max over all islands.

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def dfs(r: int, c: int) -> int:
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 0
            grid[r][c] = 0                     # sink so we never revisit
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))
        return best

Walkthrough (grid = [[1,1,0],[1,0,0],[0,0,1]]):

First 1 at (0,0): DFS sinks (0,0), spreads to (1,0) and (0,1), each dead-ending → area 3. best = 3.
Next unsunk 1 at (2,2): isolated → area 1. best = max(3,1) = 3.
Return 3.

Complexity: every cell is visited a constant number of times → O(m·n) time. Space is O(m·n) worst case for the recursion stack (a snake-shaped island).

Approach 2 — BFS flood fill

The insight: identical component-flooding, but with an explicit queue instead of recursion. Preferred when the grid is large and an island could be up to 2500 cells (50×50) deep — recursion could approach Python’s limit, while BFS keeps the frontier on the heap. DFS is shorter; BFS is the safer default for big grids. This version uses a separate visited set to leave grid intact.

from collections import deque


class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def bfs(sr: int, sc: int) -> int:
            queue = deque([(sr, sc)])
            visited.add((sr, sc))
            area = 0
            while queue:
                r, c = queue.popleft()
                area += 1
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if (
                        0 <= nr < rows
                        and 0 <= nc < cols
                        and grid[nr][nc] == 1
                        and (nr, nc) not in visited
                    ):
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            return area

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

Walkthrough (same grid): BFS from (0,0) enqueues neighbors (1,0) and (0,1); popping them adds no new land → area 3. Later (2,2) floods alone → area 1. best = 3.

Complexity: O(m·n) time, O(m·n) space for visited and the queue.

Approach 3 — Union-find

The insight: give each land cell an id, then union it with its right and down land neighbors (checking two directions suffices to connect every adjacent pair). Each disjoint set is one island; track a size array during union and the answer is the largest set. Union-find (disjoint-set union) shines when islands are also being merged incrementally, though for a static grid it ties DFS/BFS.

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        parent = {}
        size = {}

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra != rb:
                if size[ra] < size[rb]:
                    ra, rb = rb, ra
                parent[rb] = ra
                size[ra] += size[rb]

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

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    if r + 1 < rows and grid[r + 1][c] == 1:
                        union((r, c), (r + 1, c))
                    if c + 1 < cols and grid[r][c + 1] == 1:
                        union((r, c), (r, c + 1))

        return max(size.values(), default=0)

Walkthrough (same grid): cells (0,0),(0,1),(1,0) union into one set of size 3; (2,2) stays a singleton size 1. max(size.values()) = 3.

Complexity: O(m·n · α(m·n)) ≈ O(m·n) time with path compression + union by size, O(m·n) space.

Common pitfalls

Counting diagonal neighbors — connectivity is 4-directional only.
Forgetting to mark cells visited (or to sink them), which double-counts and can loop; sinking mutates the input, so use a visited set if the caller needs grid preserved.
Returning 0 incorrectly when the max should be found — initialize best = 0 so the all-water case returns 0 naturally.
In union-find, unioning only one direction (say right) misses vertical adjacencies; you need both right and down.

Pattern takeaway

Grid problems are graph problems: cell = node, orthogonal neighbors = edges, island = connected component. Flood-fill (DFS or BFS) each unvisited component and aggregate — here the max size. Reach for BFS when recursion depth could blow up on a big grid, DFS for concise code, and union-find when components merge dynamically or you want set sizes for free.