Difficulty: MediumGraphs

Max Area of Island

Problem in Plain English

Given a binary grid of land and water, find the cell count of the largest landmass connected horizontally or vertically. Grids without land score zero.

Problem Statement

You are given an m x n binary matrix grid where 1 is land and 0 is water.

An island is a group of 1s connected horizontally or vertically, and its area is its cell count. Return the largest island area, or 0 when there is no land.

Constraints

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

Examples

Example 1

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

Cells (0,0), (0,1) and (1,1) connect through shared sides. The bottom corners touch that group only diagonally, so each has area 1 and the maximum is 3.

Example 2

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

No land cell exists, so the maximum area is zero.

Example 3

Input: grid = [[1]]
Output: 1

The only cell is land, so it forms one island of area 1 even though every neighbor lies outside the grid.

Example 4

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

The land around rows 3-5 near column 8 links six cells, beating the islands of size 5, 4 and 1.

Intuition

An island is a connected component of land cells: starting at any of its cells and following only horizontal or vertical land neighbors reaches exactly that island. In Example 1, (0,0), (0,1) and (1,1) make a component of area 3, while (2,0) and (2,2) each stand alone. Count cells during a flood fill and keep the largest count. Remembering discoveries across the outer scan prevents measuring the same island again.

Approaches

Flood Per Cell

Solution Details

Reveal Flood Per Cell: intuition, complexity, and code

Intuition

Every land cell can anchor its own flood fill, and the biggest fill wins, so measuring each island separately is clearly correct. The waste is re-flooding: each island is re-explored once per land cell it holds because nothing remembers earlier visits.

Step-by-Step Logic

Scan every position in row-major order. For each land anchor, allocate a fresh visited grid and start an explicit DFS stack; Example 1 first starts at (0,0).
Mark the anchor on push. Pop a cell, increment area and push each valid unvisited land neighbor in down, up, right, left order, marking it immediately. The first fill pops (0,0), (0,1), (1,1), giving area 3.
After the stack empties, update best with this area. Retain the original grid, but discard this fill's visited grid; best becomes 3.
Repeat even for anchors inside a previously measured island. (0,1) and (1,1) each rediscover the same three cells; the bottom corners each give area 1. Return best = 3.

Why It Works

Mark a land cell when pushing it, so it can enter the stack only once in this fill. Every pushed cell is connected to the start by land-only steps. Conversely, along any land path from the start, popping a cell discovers its next unmarked neighbor; induction on path length means the whole island is reached. One increment per pop therefore measures exactly its area. The outer scan includes a start from every island, and taking the maximum of those exact areas gives the answer; an all-water grid leaves best at zero.

Dry Run

Flood Per Cell: variable states at each step
Anchor	Popped	Newly marked / stack after (top at right)	Area	Best after fill
(0,0)	start	mark (0,0); [(0,0)]	0	0
(0,0)	(0,0)	mark (0,1); [(0,1)]	1	pending
(0,0)	(0,1)	mark (1,1); [(1,1)]	2	pending
(0,0)	(1,1)	none; []	3	3
(0,1)	start	fresh seen; [(0,1)]	0	3
(0,1)	(0,1)	mark (1,1), (0,0); [(1,1),(0,0)]	1	pending
(0,1)	(0,0)	none; [(1,1)]	2	pending
(0,1)	(1,1)	none; []	3	3
(1,1)	start	fresh seen; [(1,1)]	0	3
(1,1)	(1,1)	mark (0,1); [(0,1)]	1	pending
(1,1)	(0,1)	mark (0,0); [(0,0)]	2	pending
(1,1)	(0,0)	none; []	3	3
(2,0)	start then (2,0)	mark anchor, then []; no neighbors	0 -> 1	3
(2,2)	start then (2,2)	mark anchor, then []; no neighbors	0 -> 1	3
scan ends	water positions skipped	all five land anchors measured	-	return 3

Complexity Analysis

Time Complexity

O((m \cdot n)^2)

Space Complexity

O(m \cdot n)

Let N = m times n. Each of at most N land anchors allocates a fresh N-cell visited grid and can visit N cells, so time is O(N squared), achieved on all-land input. A single visited grid and stack hold O(N) entries at a time. Java/Python/JavaScript allocate O(N squared) total temporary storage over the run, but peak reachable auxiliary storage is O(N); garbage collection may retain discarded allocations until collection. The input is preserved.

Code

Solution.java

1import java.util.ArrayDeque;2
3class Solution {4    public int maxAreaOfIsland(int[][] grid) {5        int rows = grid.length, cols = grid[0].length, best = 0;6        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};7        for (int r = 0; r < rows; r++) {8            for (int c = 0; c < cols; c++) {9                if (grid[r][c] == 0) continue;10                boolean[][] seen = new boolean[rows][cols];11                ArrayDeque<int[]> stack = new ArrayDeque<>();12                // Mark on push: converging paths must not schedule a cell twice.13                seen[r][c] = true;14                stack.push(new int[]{r, c});15                int area = 0;16                while (!stack.isEmpty()) {17                    int[] cell = stack.pop();18                    area++;19                    for (int[] d : directions) {20                        int nr = cell[0] + d[0], nc = cell[1] + d[1];21                        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;22                        if (grid[nr][nc] == 0 || seen[nr][nc]) continue;23                        seen[nr][nc] = true;24                        stack.push(new int[]{nr, nc});25                    }26                }27                best = Math.max(best, area);28            }29        }30        return best;31    }32}

Hints

Hint 1

Walk the whole grid and start measuring only at land cells you have not settled yet.

Hint 2

Count with a flood that moves up, down, left and right from each start cell.

Hint 3

Mark flooded land as visited, by sinking it to water or a second grid, so no island is ever measured twice.

Edge Cases

All water returns 0; no flood begins. A one-cell land grid returns 1.
An all-land 50 by 50 grid returns 2500. The explicit stack avoids a recursive call chain beyond Python's default recursion limit.
Diagonal contact does not connect islands: [[1,0],[0,1]] returns 1.
A one-row or one-column island is counted normally, with out-of-range neighbors ignored.
The single-pass version leaves all land as water. Reusing that same grid for another call returns 0; clone rows first if the caller needs the original.

Common Mistakes and Interview Tips

Following diagonal neighbors merges distinct islands. Use exactly the four side directions.
Marking only when popping allows several parents to push one cell; counting each pop then overestimates area.
Returning the number of fills instead of the largest area solves Number of Islands, a different problem. Reset area for each fill and keep best across fills.
Calling recursive flood fill on a 2500-cell winding island can exceed a language recursion limit; the published code uses an explicit stack.
Claiming constant auxiliary space because the grid is mutated ignores the stack. Also disclose input mutation in an interview.

Key Takeaway

Grid flood problems reward settling each cell once; sinking land or a global visited set turns repeated island walks into a single linear sweep.