grid tap a cell to toggle land / water · the run restarts · tags show each island's area
landwatervisitedframe openprobed, returns 0scan
Call stack dfs frames, bottom → top · green = count so far in that frame · red arrow = waiting on it
private int rows, cols;private int[][] grid;private boolean[][] visit;public int maxAreaOfIsland(int[][] grid) { this.grid = grid; rows = grid.length; cols = grid[0].length; visit = new boolean[rows][cols]; int area = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { area = Math.max(area, dfs(r, c)); } } return area;}private int dfs(int r, int c) { if (r < 0 || r == rows || c < 0 || c == cols || grid[r][c] == 0 || visit[r][c]) { return 0; } visit[r][c] = true; return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);}
- scan (r, c)
- —
- area
- 0
- dfs frame
- —
- depth
- 0
- visited cells
- 0
Why it works
- Same flood fill as Number of Islands, but dfs returns how many cells it painted instead of nothing: 0 for water, off-grid or visited, otherwise 1 for itself plus what its four neighbours return.
- Counts flow upward. A frame can only return once all four neighbour calls have, so the area of the whole island arrives at the first call, the one the scan made.
- Mark on entry.
visit[r][c] = truehappens before the neighbours are explored, so a cell reached twice (a ring, or two paths) returns 0 the second time and is never counted twice. - Every cell is scanned once and entered at most once: O(m·n) time.
visitand the recursion depth are O(m·n) in the worst case (one snake-shaped island). - Pitfall: the recursion is as deep as the island is long, up to m·n frames, so a very large all-land grid can throw
StackOverflowError. An explicit stack or BFS avoids it; you can also overwrite visited cells with 0 instead of keeping avisitarray. - Related: Island Perimeter (463), Making a Large Island (827), and Pacific Atlantic Water Flow (417) reuse the same grid DFS.