LeetCode · #695

Max Area of Island Solution

Given an m × n binary grid, return the maximum area (number of cells) of any island. An island is a 4-directionally connected group of 1s.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #695

🏗️

Pattern

Graph — DFS/BFS flood-fill with area count

Given a binary matrix grid of 0s (water) and 1s (land), return the maximum area of an island. An island is formed by connecting adjacent land cells horizontally or vertically. If there are no islands, return 0.

Example

 Input: grid = [[0,0,1,0],
                 [0,1,1,0],
                 [0,1,0,0]]
Output: 4 // Island of cells: (0,2),(1,1),(1,2),(2,1) — area = 4 

Constraints

 • m == grid.length,  n == grid[i].length • 1 ≤ m, n ≤ 50  ← small grid, any O(m·n) approach works • grid[i][j] is 0 or 1 (integer, not character — unlike LC 200) 

Section Two · Approach 1

DFS With Visited Array — O(m·n)

Scan every cell. When an unvisited land cell is found, run DFS to count all connected land cells (the island area). Track visited cells in a separate boolean grid. Update the global maximum after each DFS.

Why it works

Each DFS counts exactly one connected component. The outer loop finds each component exactly once (only unvisited cells trigger a DFS). Taking the max across all components gives the answer.

Why we can do better (space)

Optimization: The separate visited array uses O(m·n) extra space. Since the grid values are integers (0/1), we can overwrite visited land cells by setting them to 0 in-place — the "sink" pattern from LC 200. This reduces extra space to O(1) (only the DFS call stack remains).

Java — DFS with visited array

 class Solution {
int m, n;
boolean[][] vis;
public int maxAreaOfIsland(int[][] grid) {
        m = grid.length; n = grid[0].length;
        vis = new boolean[m][n];
int max = 0;
for (int r=0; r<m; r++)
for (int c=0; c<n; c++)
if (!vis[r][c] && grid[r][c]==1)
                    max = Math.max(max, dfs(grid,r,c));
return max;
    }
private int dfs(int[][] g, int r, int c) {
if (r<0||r>=m||c<0||c>=n||vis[r][c]||g[r][c]==0) return 0;
        vis[r][c] = true;
return 1 + dfs(g,r+1,c) + dfs(g,r-1,c)
                 + dfs(g,r,c+1) + dfs(g,r,c-1);
    }
}

Python — DFS with visited set

 class Solution:
def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        vis = set()
def dfs(r, c):
if r<0 or r>=m or c<0 or c>=n or (r,c) in vis or grid[r][c]==0: return 0
vis.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(m) for c in range(n)), default=0)

Metric	Value
Time	O(m · n)
Space	O(m · n) — visited array + O(m·n) DFS stack worst case

Section Three · Approach 2

In-place DFS — O(m·n) time, O(1) extra space

Modify the grid in-place: when visiting a cell, set it to 0 to mark it as visited. Count cells as the DFS returns up the call stack. The grid is restored to water-state for visited cells, which is acceptable since the problem doesn't require preserving input.

💡 Mental model: Imagine a biologist mapping island territories by taping off each cell they've surveyed. Instead of keeping a separate survey log, they just knock the marker pegs down (set to 0) when they survey a cell. Future passes skip knocked-down pegs automatically. The DFS return value accumulates the count bottom-up: each cell returns "1 + [area of cells reachable from me in all 4 directions]."

Algorithm — in-place flood-fill with area accumulation

Scan all cells in row-major order.
When grid[r][c] == 1: call dfs(r, c), update global max.
dfs(r, c): if out of bounds or cell is 0, return 0.
Set grid[r][c] = 0 to mark visited, then return 1 + dfs(4 neighbors).

🎯 When to recognize this pattern:

"Maximum/total area of connected regions in a grid." The DFS-return-count pattern (return 1 + recursive calls) is the standard area accumulator.
Used directly in LC 200 (count components instead of area), and extended in LC 1020 (count cells not reachable from boundary) and LC 827 (Making A Large Island — max area after flipping one 0).

Why return 1 + dfs(neighbors) works:

Each call to dfs(r, c) represents "I am visiting one cell." The 1 counts the current cell.
The recursive calls count all cells reachable from neighbors.
Since cells are zeroed before recursing, no cell is double-counted.
The sum propagates up through the call stack — the root call returns the total island area.

Section Four · Trace

Visual Walkthrough

Trace on a 3×4 grid with two islands. DFS from (0,2) finds area 4.

Max Area of Island — In-place DFS (grid: 3×4)

Section Five · Implementation

Code — Java & Python

Java — In-place DFS area count

 class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length, max = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1)
                    max = Math.max(max, dfs(grid, r, c));
return max;
    }
private int dfs(int[][] g, int r, int c) {
if (r < 0 || r >= g.length ||
            c < 0 || c >= g[0].length ||
            g[r][c] == 0) return 0;
        g[r][c] = 0; // mark visited in-place return 1 + dfs(g,r+1,c) + dfs(g,r-1,c)
                 + dfs(g,r,c+1) + dfs(g,r,c-1); // 1 + area of all neighbors
}
}

Python — In-place DFS area count

 class Solution:
def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
def dfs(r: int, c: int) -> int:
if r < 0 or r >= m or c < 0 or c >= n 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)
return max(
            (dfs(r, c) for r in range(m) for c in range(n) if grid[r][c]),
            default=0
)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS + visited boolean array	O(m · n)	O(m · n)	Preserves input; extra O(m·n) space
BFS in-place	O(m · n)	O(min(m,n)) queue	Iterative — no stack overflow risk; more code
DFS in-place ← optimal	O(m · n)	O(m · n) DFS stack	Minimal code; mutates input acceptably; elegant return-1+neighbors pattern

Note on DFS stack space:

In the worst case (all land, single snake-shaped island of 2500 cells), DFS stack depth = 2500 — safe for the given constraints (50×50).
For grids up to 300×300 (LC 200), BFS is the safer choice to avoid stack overflow.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All water	All `0`s	No DFS triggered. Return 0.
All land	All `1`s	One giant island. DFS from (0,0) returns m·n.
1×1 land	`[[1]]`	dfs returns 1. max=1.
Two equal-sized islands	Two separate 3-cell islands	DFS for each returns 3. Max stays 3.
Diagonal land cells	1s only diagonally adjacent	Diagonal adjacency is not connected — each diagonal cell is a separate island of size 1.
Input uses chars vs ints	`'0'/'1'` vs `0/1`	LC 200 uses chars; LC 695 uses ints. Check comparison: `== 1` not `== '1'`.

⚠ Common Mistake: Not handling the all-water grid case when using max() without a default. In Python, max(empty_iterable) raises a ValueError. Always provide default=0 — the answer is 0 if no islands exist. Alternatively, initialize maxArea = 0 and update it only when a land cell is found.

← Back to Graph problems

LearningTree

LC 695 · Max Area of Island — Solution & Explanation | DSA Guide