695 - Max Area of Island

Difficulty: Medium | Pattern: DFS / BFS on Grid | Company tags: Amazon, Facebook, Google, Microsoft

Problem Statement

You are given an m x n binary matrix grid. An island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical). The area of an island is the number of cells with value 1 in it.

Return the maximum area of an island in grid. If there is no island, return 0.

Example:

Input:
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
        [0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,1,1,0,1,0,0,0,0,0,0,0,0],
        [0,1,0,0,1,1,0,0,1,0,1,0,0],
        [0,1,0,0,1,1,0,0,1,1,1,0,0],
        [0,0,0,0,0,0,0,0,0,0,1,0,0],
        [0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

Approach: DFS — O(m×n)

Key insight: For each unvisited land cell, run DFS to count the connected island's area. Sink visited cells (set to 0) to avoid revisiting. Track the maximum area found.

def maxAreaOfIsland(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    
    def dfs(r, c) -> 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: mark visited
        return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
    
    max_area = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))
    
    return max_area

Non-Destructive Variant (visited set)

If you cannot modify the input grid:

def maxAreaOfIsland(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()
    
    def dfs(r, c) -> int:
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == 0 or (r, c) in visited):
            return 0
        visited.add((r, c))
        return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
    
    return max(dfs(r, c) for r in range(rows) for c in range(cols))

Dry Run

Small grid: [[1,1,0],[0,1,0],[0,0,0]]

Step	Cell	Action	Running area
Start	(0,0) = 1	dfs(0,0) → sink, area=1	1
	(1,0) from (0,0)	= 0, return 0
	(-1,0) from (0,0)	out of bounds, return 0
	(0,1) from (0,0)	= 1, sink, area=1	2
	(1,1) from (0,1)	= 1, sink, area=1	3
	(2,1) from (1,1)	= 0, return 0
	(0,1) from (1,1)	already 0, return 0

Island at (0,0) area = 3. No other 1s → max_area = 3

Edge Cases

• All zeros → return 0
• All ones → entire grid is one island, area = m × n
• Single cell island → 1
• Multiple islands same size → return that size

Complexity

	Time	Space
Destructive (sink)	O(m×n)	O(m×n) stack
Non-destructive	O(m×n)	O(m×n) visited set + stack

Related: LeetCode 200 (Number of Islands) — same pattern but counts island count instead of max area.