You are given an m x n binary grid where 1 is land and 0 is water. An island is a group of 1s connected horizontally or vertically, and its area is the number of cells in it. Return the largest island area, or 0 if there is no land.
Example 1
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
The island on the right side made of cells in rows 3 to 5 has 6 cells. Diagonal cells do not join islands.
Example 2
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Constraints
- 1 <= m, n <= 50
- grid[i][j] is 0 or 1
Hints
Frequently asked at: Amazon, Google, Meta, Bloomberg
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Same idea as Number of Islands: each island is a connected component of land cells. Scan the grid, and when you hit unvisited land, run a DFS or BFS that marks the whole island as visited while counting the cells it visits. That count is the island's area. The answer is the largest count seen. Every cell is visited once, so it is linear.
Algorithm
- Loop over every cell; skip water and visited cells.
- From a new land cell, run an iterative DFS, setting cells to 0 as you push them.
- Count how many cells the DFS pops: that is the area.
- Update the best area and continue the scan.
Time:
O(m * n)Space: O(m * n) for the stack in the worst caseInterview tip: If the interviewer says you must not modify the input, use a separate
visited boolean grid. Mention this trade-off before you start sinking cells in place.class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) best = 0 for r in range(m): for c in range(n): if grid[r][c] != 1: continue area = 0 stack = [(r, c)] grid[r][c] = 0 while stack: x, y = stack.pop() area += 1 # one more cell of this island for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)): if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1: grid[nx][ny] = 0 stack.append((nx, ny)) best = max(best, area) return bestCtrl + Enter runs the examples