695. Max Area of Island

695

MediumGraph DFS and BFSDFS on a gridFlood fill for component size

Max Area of Island

Given an m x n binary grid where 1 represents land and 0 represents water, an island is a group of 1s connected 4-directionally. Return the area (number of cells) of the largest island, or 0 if there is no land.

Open official problem prompt ↗

In plain English

Measure the largest blob of connected land in the grid.

Picture it like this

Like spilling paint on one land tile and watching it spread to every touching land tile; you measure how big the painted patch grows, then compare patches and keep the biggest.

Example

Input: grid = [[0,0,1,0,0],[0,1,1,0,0],[0,0,0,1,1]]
Output: 3
Why: The upper island {(0,2),(1,1),(1,2)} has 3 cells while the other island {(2,3),(2,4)} has 2, so the max area is 3.

Constraints

m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j] is either 0 or 1

Pattern lesson

See the pattern, then code

Flood fill for component size

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. From each unvisited land cell, run a DFS that counts every connected land cell and sinks it (set to 0) so it is not revisited. Track the maximum count returned.

New words, made simpleKnow these before the algorithm

Flood fill: Recursively spreading from a cell to all connected same-value cells.
Sinking: Setting a visited land cell to 0 so it is never counted twice.
Island area: The number of connected land cells in one component.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Best choiceDFS flood fill

Clean and linear; every cell is touched once.

From each land cell, recursively count and sink its whole island, tracking the max.

Time O(m*n)Space O(m*n)

BFS flood fill

Equally optimal and avoids recursion-depth limits on large grids.

Same idea but with an explicit queue instead of recursion.

Time O(m*n)Space O(m*n)

Union-Find

Works but is heavier than a simple traversal for a one-shot query.

Union adjacent land cells then take the largest set size.

Time O(m*n * alpha)Space O(m*n)

The rule we keep true

Invariant

Once a land cell is sunk to 0 it is counted in exactly one island's area, so no cell contributes to more than one measurement.

Why this is correct

Reasoning

A DFS launched from a land cell reaches precisely the cells of its island; sinking guarantees each cell is counted once. Taking the maximum over all launches yields the largest island's area. Cells already sunk are skipped by the outer scan.

The algorithm in three movesSay these aloud before coding

1Scan the grid for a land cell

dfs at (0,2): 1 + down(1,2)

2DFS from it, returning 1 plus the areas of its four neighbors

(1,2): 1 + left(1,1)

3Sink each visited cell to 0 to avoid recount

area of upper island = 3, best = 3

4Update the running maximum with each island's area

5Return the maximum found

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readrow 0

2 · AskFirst land cell?

3 · Update statefound (0,2)=1

4 · Resultlaunch DFS

Key takeaway

The connected land cells (0,2),(1,1),(1,2) form the largest island of area 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-6DFS base case
Out-of-bounds or water contributes 0 area and stops the branch.
2
Lines 7-8Sink and count
Mark the cell as water, then add 1 plus the areas of all four neighbors.
3
Lines 11-16Scan and maximize
Every remaining land cell starts a fresh island measurement; keep the largest.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A grid with no land at all -> 0
A single land cell -> 1
The entire grid being land -> m*n
Diagonally touching land cells count as separate islands since only 4-directional links join them

Common beginner mistakes

Counting diagonal neighbors, which incorrectly merges separate islands
Failing to sink cells, causing infinite recursion or double counting
Mutating the grid when the caller needs it preserved (copy it if so)
Recursion depth on a 50x50 all-land grid can be large; an explicit stack or BFS is safer

Check your understanding

Why is it acceptable to overwrite the grid with 0s during the search?

PyPython 3 · solution.py

Optimal

1class Solution:2    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:3        m, n = len(grid), len(grid[0])45        def dfs(r: int, c: int) -> int:6            if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] == 0:7                return 08            grid[r][c] = 09            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)1011        best = 012        for r in range(m):13            for c in range(n):14                if grid[r][c] == 1:15                    best = max(best, dfs(r, c))16        return best

Time complexityO(m * n)Optimized

Space complexityO(m * n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMeta

Max Area of Island

Max Area of Island

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS