#695
Max Area of Island
Medium DFS returning size
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a 0/1 grid, return the area (number of cells) of the largest island, or 0.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the size of the biggest island.
Why this works: same as counting islands, but the DFS returns how many cells it sank.
Example: an island of 4 cells and one of 6
answer 6✦Hints open one at a time
Same as Number of Islands, but DFS returns how many cells it sank.
Area = 1 + areas of the four directions.
↗Approach
For each land cell, run the sinking DFS that returns the size, and keep the maximum.
</>Solution (Java)
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++)
best = Math.max(best, area(grid, r, c));
return best;
}
private int area(int[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] == 0) return 0;
g[r][c] = 0;
return 1 + area(g, r + 1, c) + area(g, r - 1, c) + area(g, r, c + 1) + area(g, r, c - 1);
}
}!Common mistake
Not marking cells as visited before recursing, so cells are counted multiple times.
Complexity
- Time: O(m·n).
- Space: O(m·n).
Topic: Graphs
🎬 Episodes 74–85: video coming soon