695. Max Area of Island (Medium)

Problem

Given a binary 2D grid where 1 is land and 0 is water, return the maximum area of an island. An island is a connected set of 1s (4-directional).

Example

• A 51-island grid like the one in the problem → 6
• grid = [[0, 0, 0, 0, 0, 0, 0, 0]] → 0

LeetCode 695 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: DFS returning island area

Same template as Number of Islands, but the DFS returns the size of the connected component instead of just marking it.

Python

def max_area_of_island(grid):
    if not grid:                                                         # L1: guard empty input
        return 0
    rows, cols = len(grid), len(grid[0])                                 # L2: grid dimensions

    def dfs(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:   # L3: bounds + land check
            return 0
        grid[r][c] = 0                                                   # L4: mark visited
        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)  # L5: sum neighbors

    best = 0
    for r in range(rows):                                                # L6: outer scan
        for c in range(cols):                                            # L7: inner scan
            if grid[r][c] == 1:
                best = max(best, dfs(r, c))                              # L8: launch DFS, update best
    return best

TypeScript

function maxAreaOfIsland(grid: number[][]): number {
    if (!grid.length) return 0;                                          // L1: guard empty input
    const rows = grid.length, cols = grid[0].length;                     // L2: grid dimensions

    function dfs(r: number, c: number): number {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== 1) return 0;  // L3
        grid[r][c] = 0;                                                  // L4: mark visited
        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);  // L5
    }

    let best = 0;
    for (let r = 0; r < rows; r++) {                                     // L6: outer scan
        for (let c = 0; c < cols; c++) {                                 // L7: inner scan
            if (grid[r][c] === 1) best = Math.max(best, dfs(r, c));      // L8: launch DFS
        }
    }
    return best;
}

Swift

final class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        let rows = grid.count, cols = grid[0].count
        var seen = Set<Int>()
        func area(_ row: Int, _ col: Int) -> Int {
            let key = row * cols + col
            if row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == 0 || !seen.insert(key).inserted { return 0 }
            return 1 + area(row + 1, col) + area(row - 1, col) + area(row, col + 1) + area(row, col - 1)
        }
        var best = 0
        for row in 0..<rows { for col in 0..<cols { best = max(best, area(row, col)) } }
        return best
    }
}

Where the time goes, line by line

Variables: m = grid rows, n = grid cols.

Line	Per-call cost	Times executed	Contribution
L6, L7 (scan)	$O(1)$	m * n	$O(m * n)$
L3 (bounds check)	$O(1)$	once per DFS call	$O(m * n)$ total
L4 (mark visited)	$O(1)$	once per land cell	$O(m * n)$ total
L5 (recurse 4 neighbors)	$O(1)$ per frame	each cell visited once	$O(m * n)$ ← dominates
L8 (max update)	$O(1)$	m * n	$O(m * n)$

Each cell is visited at most once: L4 marks it 0 before recursing, so no cell is processed twice. Total work across all DFS calls is proportional to the number of cells.

Complexity

• Time: $O(m * n)$, driven by L5 (each cell entered at most once across all DFS calls).
• Space: $O(m * n)$ recursion worst case (a fully-land grid produces a call stack m * n deep).

Approach 2: BFS with area counting

Equivalent structure; avoids deep recursion.

Python

from collections import deque

def max_area_of_island(grid):
    if not grid:                                             # L1: guard empty input
        return 0
    rows, cols = len(grid), len(grid[0])                     # L2: grid dimensions
    best = 0

    for r in range(rows):                                    # L3: outer scan
        for c in range(cols):                                # L4: inner scan
            if grid[r][c] != 1:
                continue
            area = 0
            q = deque([(r, c)])                              # L5: seed queue
            grid[r][c] = 0                                   # L6: mark visited immediately
            while q:
                x, y = q.popleft()                           # L7: O(1) dequeue
                area += 1                                    # L8: count this cell
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                        grid[nx][ny] = 0                     # L9: mark before enqueue
                        q.append((nx, ny))                   # L10: O(1) enqueue
            best = max(best, area)                           # L11: update global best
    return best

TypeScript

function maxAreaOfIsland(grid: number[][]): number {
    if (!grid.length) return 0;                                          // L1: guard empty input
    const rows = grid.length, cols = grid[0].length;                     // L2: grid dimensions
    let best = 0;

    for (let r = 0; r < rows; r++) {                                     // L3: outer scan
        for (let c = 0; c < cols; c++) {                                 // L4: inner scan
            if (grid[r][c] !== 1) continue;
            let area = 0;
            const q: [number, number][] = [[r, c]];                      // L5: seed queue
            grid[r][c] = 0;                                              // L6: mark visited immediately
            let head = 0;
            while (head < q.length) {
                const [x, y] = q[head++];                                // L7: O(1) dequeue
                area++;                                                  // L8: count this cell
                for (const [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
                    const nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] === 1) {
                        grid[nx][ny] = 0;                                // L9: mark before enqueue
                        q.push([nx, ny]);                                // L10: O(1) enqueue
                    }
                }
            }
            best = Math.max(best, area);                                 // L11: update global best
        }
    }
    return best;
}

Swift

final class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        let rows = grid.count, cols = grid[0].count
        var seen = Set<Int>(), best = 0
        for row in 0..<rows { for col in 0..<cols where grid[row][col] == 1 && !seen.contains(row * cols + col) {
            var queue = [(row, col)], head = 0, area = 0
            seen.insert(row * cols + col)
            while head < queue.count {
                let (r, c) = queue[head]; head += 1; area += 1
                for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                    let nr = r + dr, nc = c + dc, key = nr * cols + nc
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && seen.insert(key).inserted { queue.append((nr, nc)) }
                }
            }
            best = max(best, area)
        } }
        return best
    }
}

Complexity

• Time: $O(m * n)$, driven by L7/L10 (each land cell enqueued and dequeued exactly once).
• Space: $O(min(m, n)$) queue frontier.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
DFS with area return	$O(m * n)$	$O(m * n)$ recursion
BFS with area counter	$O(m * n)$	$O(min(m, n)$)
Union-Find with sizes	$O(m * n * alpha)$	$O(m * n)$

The DFS-return-area pattern is the cleanest here, it generalizes to “for each component, compute some aggregate” (sum, min, max, perimeter).

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_695.py and run.
# Uses the canonical implementation (Approach 1: DFS).

def max_area_of_island(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
            return 0
        grid[r][c] = 0
        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

def _run_tests():
    # Example from problem statement: largest island has area 6
    assert max_area_of_island([
        [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],
    ]) == 6

    # All water
    assert max_area_of_island([[0, 0, 0, 0, 0, 0, 0, 0]]) == 0

    # Single land cell
    assert max_area_of_island([[1]]) == 1

    # Single water cell
    assert max_area_of_island([[0]]) == 0

    # Two disconnected islands of different sizes
    assert max_area_of_island([
        [1, 0, 0, 1, 1],
        [1, 0, 0, 0, 1],
    ]) == 3

    # Entire grid is one island
    assert max_area_of_island([
        [1, 1],
        [1, 1],
    ]) == 4

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function maxAreaOfIsland(grid: number[][]): number {
    if (!grid.length) return 0;
    const rows = grid.length, cols = grid[0].length;

    function dfs(r: number, c: number): number {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== 1) return 0;
        grid[r][c] = 0;
        return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1);
    }

    let best = 0;
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++)
            if (grid[r][c] === 1) best = Math.max(best, dfs(r, c));
    return best;
}

console.assert(maxAreaOfIsland([[0,0,0,0,0,0,0,0]]) === 0);
console.assert(maxAreaOfIsland([[1]]) === 1);
console.assert(maxAreaOfIsland([[0]]) === 0);
console.assert(maxAreaOfIsland([[1,0,0,1,1],[1,0,0,0,1]]) === 3);
console.assert(maxAreaOfIsland([[1,1],[1,1]]) === 4);
console.log("all tests pass");

Related data structures

• Arrays, the grid
• Queues, BFS

Related concepts

• DFS, depth-first traversal tactics for exploring one branch fully before backtracking to alternatives.
• Flood Fill, grid traversal tactics for expanding through adjacent cells that share a condition.