MediumNeetCode150ArrayDepth-First SearchBreadth-First SearchMatrix
Max Area of Island
Return max area of an island.
Examples
Input
grid = [[0,0,1,0,0,...],[...]]
Output
6
Largest island area is 6.
Constraints
- •
m,n <= 50 - •
grid[i][j] is 0 or 1
Approaches
Count cells in each island.
CodeT: O(m*n) | S: O(m*n) worst case
def maxAreaOfIsland(grid):
r=len(grid); c=len(grid[0]); mx=0
def dfs(i,j):
if i<0 or i>=r or j<0 or j>=c or grid[i][j]!=1: return 0
grid[i][j]=0
return 1+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1)
for i in range(r):
for j in range(c):
if grid[i][j]==1: mx=max(mx,dfs(i,j))
return mxCodeT: O(m*n) | S: O(min(m,n))
Stack-based.
CodeT: O(m*n) | S: O(m*n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS | O(m*n) | O(m*n) worst case | Count cells in each island. |
| BFS | O(m*n) | O(min(m,n)) | |
| DFS Iterative | O(m*n) | O(m*n) | Stack-based. |
DFS
T: O(m*n)S: O(m*n) worst case
Count cells in each island.
BFS
T: O(m*n)S: O(min(m,n))
DFS Iterative
T: O(m*n)S: O(m*n)
Stack-based.
Common Mistakes
Not resetting visited cells
Counting wrong area
Not handling empty grid