#695 Max Area of Island
frequently reported atIntuitMetaAmazonGoogleBloombergMicrosoft
the problem
In plain words
A grid holds 1 (land) and 0 (water). Land cells join up, down, left and right — never diagonally — and the grid's outside is water. An island's area is its number of land cells. Return the biggest area, or 0 if there is no land.
in 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]]
out 6
The island in rows 3–5, columns 8–10 has 6 cells. Nothing is bigger, because cells that touch only at a corner don't join.
in grid = [[0,0,0,0,0,0,0,0]]
out 0
No land at all.
- 1 ≤ m, n ≤ 50
- grid[i][j] is 0 or 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGrid flood fill
It's Number of Islands with one change: the flood fill returns how many cells it sank. Area of a cell's island = 1 + the areas found in its 4 directions. Keep the maximum.
solutions
From brute force to optimal
For each land cell, BFS its whole island with a fresh visited grid and count the cells. Keep the biggest count.
- Loop over every cell.
- On a 1: BFS through land neighbours with a brand-new
seengrid; count polled cells. - best = max(best, count).
An island of k cells is re-measured k times. One big island of m·n cells costs m·n BFS runs of m·n each.
A fresh seen grid plus the queue for one BFS.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; /** For every land cell, BFS its whole island again with a fresh visited grid. */ public int maxAreaOfIsland(int[][] grid) { int rows = grid.length, cols = grid[0].length, best = 0; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 1) best = Math.max(best, islandSize(grid, r, c)); return best; } private int islandSize(int[][] grid, int sr, int sc) { int rows = grid.length, cols = grid[0].length, size = 0; boolean[][] seen = new boolean[rows][cols]; // fresh every time: that's the waste Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[] {sr, sc}); seen[sr][sc] = true; while (!queue.isEmpty()) { int[] cell = queue.poll(); size++; for (int[] d : DIRS) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue; if (grid[nr][nc] != 1 || seen[nr][nc]) continue; seen[nr][nc] = true; queue.offer(new int[] {nr, nc}); } } return size; }}Scan once. Each untouched land cell starts a DFS that sinks its island and returns its size, so every cell is counted exactly once.
- best = 0; loop over all cells.
- On a 1: area = sink(r, c); best = max(best, area).
- sink returns 0 for out of bounds or water; otherwise sets the cell to 0 and returns 1 + sink of the 4 neighbours.
Each cell is scanned once and sunk at most once; each sink tries 4 neighbours.
If the whole grid is one island, the recursion can go m·n deep.
class Solution { public int maxAreaOfIsland(int[][] grid) { int best = 0; for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++) if (grid[r][c] == 1) { int area = sink(grid, r, c); best = Math.max(best, area); } return best; } /** Sinks the island containing (r, c) and returns how many cells it had. */ private int sink(int[][] grid, int r, int c) { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != 1) return 0; grid[r][c] = 0; // sinking doubles as the visited mark return 1 + sink(grid, r + 1, c) + sink(grid, r - 1, c) + sink(grid, r, c + 1) + sink(grid, r, c - 1); }}Dry run
Same scan, but measure each island with a queue: count every cell you poll. No recursion depth to worry about.
- On a 1: sink it, enqueue it, area = 0.
- Poll: area++; sink and enqueue every land neighbour.
- When the queue empties, best = max(best, area).
Each cell enters the queue at most once.
The queue holds at most the cells of one island.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; /** Same scan, but each island is measured with a queue — no recursion depth limit. */ public int maxAreaOfIsland(int[][] grid) { int rows = grid.length, cols = grid[0].length, best = 0; Deque<int[]> queue = new ArrayDeque<>(); for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { if (grid[r][c] != 1) continue; int area = 0; grid[r][c] = 0; // sink on enqueue so no cell is counted twice queue.offer(new int[] {r, c}); while (!queue.isEmpty()) { int[] cell = queue.poll(); area++; for (int[] d : DIRS) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] != 1) continue; grid[nr][nc] = 0; queue.offer(new int[] {nr, nc}); } } best = Math.max(best, area); } return best; }}in the room
How to say it in the interview
talk track
- Say: "This is Number of Islands, but the flood fill returns a size instead of just marking."
- Ask if you may modify the grid; if not, use a
boolean[][] seeninstead of sinking. - State O(m·n) time. Mention recursion depth up to m·n = 2,500 here, and the BFS version if the grid were huge.
traps
- Counting cells in a field that every DFS call shares, then forgetting to reset it for the next island.
- Checking
grid[r][c]before the bounds check →ArrayIndexOutOfBoundsException. - Not sinking (or marking) a cell before recursing — neighbours walk back into it and the count grows forever.
what they ask next
Follow-ups
Making A Large Island (LC 827): flip at most one 0 to 1. Biggest island now?
Label each island with an id and store its area. For each 0, add up the areas of the distinct island ids around it, plus 1. Take the max (or the whole grid if it's all land).
Count islands and report each one's size?
Same scan; store each returned area in a list instead of keeping only the max.
before you submit
Edge cases to test
- No land at all → 0.
- The whole grid is land → m·n (and the deepest recursion).
- Cells touching only at a corner are separate islands.
- An island shaped like a ring around a lake still counts every land cell once.
practise next
Similar problems
- #200Number of IslandsMediumin Graphs
- #130Surrounded RegionsMediumin Graphs
- #733Flood FillEasyin Graphs