Problem Breakdown
We are given a 2D grid representing land (1) and water (0). An island is defined as any group of 1s connected horizontally or vertically (4-directional). Our goal is to find the maximum area among all islands. The “area” corresponds to the count of cells in that specific island component.
Inputs:
- A 2D list of integers (
grid), where values are either0or1. - Dimensions up to .
Outputs:
- An integer representing the maximum area found. Returns
0if no islands exist (all water).
Implicit Constraints & Edge Cases:
- Connectivity: Only orthogonal neighbors count; diagonal connections do not form an island.
- Visited State: Once a cell is counted as part of an island, it cannot be reused for another area calculation to avoid double-counting within the same traversal or across different islands if we don’t mark them visited.
- Empty/All Water Grids: Must return
0. - Grid Boundaries: We must ensure neighbor checks do not go out of bounds (row index or , col index or ).
Intuition
A naive approach might be to iterate through every cell. If we find a 1, we count it and its neighbors recursively until the island ends, then reset counters for other islands. However, if we don’t mark cells as visited during this process, we will re-count the same land mass multiple times when our outer loop encounters different parts of that same island later on.
Brute Force Complexity:
If we simply count connected components without marking visited nodes (e.g., using a visited set), or if we iterate through every cell and run BFS/DFS from every unvisited land cell, the complexity becomes in worst-case scenarios where many islands overlap conceptually but are distinct. More simply, without marking visited cells as water (0) during traversal, we risk exponential time due to redundant traversals of the same component.
Key Insight:
We need a “visited” mechanism. Since modifying the input grid is allowed and saves space (we don’t need it later), we can turn 1s into 0s once they are visited. This effectively marks them as processed water, preventing us from counting them again in future iterations of our outer loop or within the same DFS traversal.
Approach
- Initialize a variable
max_areato store the largest island found so far (default0). - Iterate through every cell
(row, col)in the grid using nested loops. - If we encounter a land cell (
grid[row][col] == 1):- This is part of an unexplored island. Start a Depth-First Search (DFS) from this position to calculate its total area.
- During DFS, increment the current island’s counter for every valid neighbor that is also land (
1). - Crucially, mark visited cells as water (
0) immediately upon visiting them so they aren’t counted again in future steps or by other branches of the same traversal.
- Update
max_areawith the result from this specific island’s DFS if it exceeds the current maximum. - Continue until all grid cells are checked. Return
max_area.
Complexity Analysis
- Time Complexity: , where is rows and is columns. We visit each cell at most twice: once in the outer loop check and potentially once during a DFS traversal (where we mark it visited). Since every
1becomes0, no land cell triggers multiple full traversals. - Space Complexity: auxiliary space if we modify the input grid to track visited status, excluding recursion stack overhead. If considering Python’s call stack for recursive DFS in a snake-like island pattern, it is technically due to the maximum depth of the recursion tree being bounded by the longest path (though typically limited by ). Given constraints (), this fits well within standard limits.
Solution
class Solution:
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
max_area = 0
def dfs(r, c):
# Base cases for recursion boundaries and water cells
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
# If current cell is land (1), process it.
# Mark as visited by setting to 0 immediately to avoid double counting.
grid[r][c] = 0
area = 1 + dfs(r - 1, c) + \
dfs(r + 1, c) + \
dfs(r, c - 1) + \
dfs(r, c + 1)
return area
# Iterate over every cell in the grid
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
current_area = dfs(r, c)
max_area = max(max_area, current_area)
return max_area
Edge Cases Handled
- All Water Grid: The outer loop finds no
1s; returns initialmax_areaof0. Correct. - Single Island vs Multiple Islands: DFS naturally isolates components because we mark cells as visited (
0). Once an island is fully traversed, subsequent iterations in the main loops skip its remaining parts (now marked water). - Boundary Conditions: The recursive function checks indices against
rowsandcolsbefore accessing neighbors. This prevents index out of bounds errors on edges or corners. - Recursion Depth: While Python has a recursion limit, for grids the maximum depth is manageable within standard limits (typically ~1000), though iterative DFS would be used in production systems requiring strict memory safety against deep snake-like paths.