The problem
A grid holds 1 for land and 0 for water; an island is land cells joined horizontally or vertically. Its area is its number of cells. Return the largest area, or 0 if there is no land.
Examples
01
- 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
02
- Input
grid = [[0, 0, 0, 0, 0, 0, 0, 0]]
- Output
0
Constraints
- 1 ≤ m, n ≤ 50
- Each cell is 0 or 1.
The idea
This is Number of Islands, counting cells instead of islands. When the scan meets land, a depth-first search spreads over the whole island, sinking each cell as it goes and counting one for each.
The count when the search runs out is that island’s area; keep the largest.
- Time
- O(m · n)
- Space
- O(m · n)
Solution · every language run against every case
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: rows, cols = len(grid), len(grid[0]) best = 0 for r in range(rows): for c in range(cols): if grid[r][c] != 1: continue grid[r][c] = 0 # sink each square as it is counted, so none is counted twice stack, area = [(r, c)], 0 while stack: i, j = stack.pop() area += 1 for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)): if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 1: grid[x][y] = 0 stack.append((x, y)) best = max(best, area) return best