LeetCode 695: Max Area of Island (DFS Flood Fill Area Accumulation)
LeetCode 695DFSMatrixFlood FillToday we solve LeetCode 695 - Max Area of Island.
Source: https://leetcode.com/problems/max-area-of-island/
English
Problem Summary
Given a binary grid where 1 is land and 0 is water, return the maximum area of an island. An island is formed by 4-directionally connected lands.
Key Insight
Each island area is exactly the number of cells visited during one DFS/BFS flood fill. If we mark visited land in-place, every land cell is counted once globally.
Brute Force and Limitations
You could start DFS from every land cell without a visited strategy, but that repeats work and explodes runtime. The correct approach is one-pass scanning + one flood fill per unvisited island root.
Optimal Algorithm Steps
1) Iterate all cells.
2) When cell is 1, start DFS and set it to 0 immediately.
3) DFS returns 1 + areas from valid 4 neighbors.
4) Update global maximum with current island area.
5) Continue scan until all cells processed.
Complexity Analysis
Time: O(mn) because each cell is visited at most once.
Space: O(mn) worst case recursion stack (all land), typically less.
Common Pitfalls
- Forgetting to mark visited before recursive expansion (double count / infinite recursion).
- Using diagonal neighbors (problem allows only up/down/left/right).
- Resetting max incorrectly instead of taking max(maxArea, area).
- Ignoring empty grid edge case.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int best = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
best = Math.max(best, dfs(grid, r, c));
}
}
}
return best;
}
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;
return 1 + dfs(g, r + 1, c) + dfs(g, r - 1, c) + dfs(g, r, c + 1) + dfs(g, r, c - 1);
}
}func maxAreaOfIsland(grid [][]int) int {
m, n := len(grid), len(grid[0])
var dfs func(int, int) int
dfs = func(r, c int) int {
if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 {
return 0
}
grid[r][c] = 0
return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
}
best := 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if grid[r][c] == 1 {
area := dfs(r, c)
if area > best {
best = area
}
}
}
}
return best
}class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), best = 0;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (grid[r][c] == 1) {
best = max(best, dfs(grid, r, c));
}
}
}
return best;
}
int dfs(vector<vector<int>>& g, int r, int c) {
if (r < 0 || r >= (int)g.size() || c < 0 || c >= (int)g[0].size() || g[r][c] == 0) return 0;
g[r][c] = 0;
return 1 + dfs(g, r + 1, c) + dfs(g, r - 1, c) + dfs(g, r, c + 1) + dfs(g, r, c - 1);
}
};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
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
best = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
best = max(best, dfs(r, c))
return bestvar maxAreaOfIsland = function(grid) {
const m = grid.length, n = grid[0].length;
function dfs(r, c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === 0) return 0;
grid[r][c] = 0;
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
}
let best = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
best = Math.max(best, dfs(r, c));
}
}
}
return best;
};中文
题目概述
给定一个只含 0/1 的网格，1 代表陆地，0 代表海水。岛屿由上下左右四联通的陆地组成，求最大岛屿面积。
核心思路
每个岛屿面积就是一次 DFS/BFS 淹没搜索访问到的陆地数量。把访问过的陆地原地改为 0，可确保每个格子只统计一次。
暴力解法与不足
如果对每个陆地都重复启动且不做访问标记，会出现大量重复遍历。正确做法是扫描网格，仅在遇到“未访问陆地”时启动一次洪泛搜索。
最优算法步骤
1）遍历所有网格位置。
2）若当前是 1，立刻标记为 0 并进入 DFS。
3）DFS 返回 1 + 四邻域面积之和。
4）用当前面积更新全局最大值。
5）继续遍历直到结束。
复杂度分析
时间复杂度：O(mn)，每个格子最多访问一次。
空间复杂度：最坏 O(mn)（递归栈全陆地时）。
常见陷阱
- 没有在递归前标记访问，导致重复计数或死循环。
- 错把对角线当连通方向（题目仅四方向）。
- 更新答案时覆盖写错，没有使用最大值比较。
- 忽略空网格等边界输入。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int best = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
best = Math.max(best, dfs(grid, r, c));
}
}
}
return best;
}
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;
return 1 + dfs(g, r + 1, c) + dfs(g, r - 1, c) + dfs(g, r, c + 1) + dfs(g, r, c - 1);
}
}func maxAreaOfIsland(grid [][]int) int {
m, n := len(grid), len(grid[0])
var dfs func(int, int) int
dfs = func(r, c int) int {
if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 {
return 0
}
grid[r][c] = 0
return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
}
best := 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if grid[r][c] == 1 {
area := dfs(r, c)
if area > best {
best = area
}
}
}
}
return best
}class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), best = 0;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (grid[r][c] == 1) {
best = max(best, dfs(grid, r, c));
}
}
}
return best;
}
int dfs(vector<vector<int>>& g, int r, int c) {
if (r < 0 || r >= (int)g.size() || c < 0 || c >= (int)g[0].size() || g[r][c] == 0) return 0;
g[r][c] = 0;
return 1 + dfs(g, r + 1, c) + dfs(g, r - 1, c) + dfs(g, r, c + 1) + dfs(g, r, c - 1);
}
};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
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
best = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
best = max(best, dfs(r, c))
return bestvar maxAreaOfIsland = function(grid) {
const m = grid.length, n = grid[0].length;
function dfs(r, c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === 0) return 0;
grid[r][c] = 0;
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
}
let best = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
best = Math.max(best, dfs(r, c));
}
}
}
return best;
};
Comments