You are given grid, a map made of 1s (land) and 0s (water). An island is a group of land
cells joined up, down, left or right, and its area is the number of cells in it.
Return the area of the largest island, or 0 if there is no land at all.
Example 1
- Input
- grid = [[0, 1, 1, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 1], [1, 1, 0, 1, 0]]
- Output
- 4
Example 2
- Input
- grid = [[0, 0, 0], [0, 0, 0]]
- Output
- 0
Constraints
- The grid has 1 to 200 rows and 1 to 200 columns.
- Every cell is
0or1.
Show the pattern
Graphs
The islands are the connected components of a grid graph, so a flood fill from each new land cell visits one whole island. Counting the cells each fill visits gives every island's size.
See graphs in a visualiserShow the approach
Scan the grid. At each land cell, flood-fill its island with a stack: sink the starting cell (set
it to 0) and push it, then repeatedly pop a cell, add one to the area, and push each neighbour
that is on the grid and still land, sinking it as you push it. When the stack is empty, the area
is the island's size; keep the largest.
Each cell is pushed at most once, so the whole scan is linear in the size of the grid. An explicit stack avoids deep recursion on a big island.
Time: O(rows · cols) · Space: O(rows · cols) for the stack in the worst case