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; cells that only touch diagonally are not joined. Everything
outside the grid is water.
Return the number of islands.
Example 1
- Input
- grid = [[1, 1, 0, 0, 1], [0, 1, 0, 1, 1], [1, 0, 0, 0, 0], [1, 0, 1, 1, 0]]
- Output
- 4
Example 2
- Input
- grid = [[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
Land cells joined side by side form groups, and counting the groups is counting the connected components of a graph whose nodes are cells. Each new land cell starts a flood fill that claims its whole island.
See graphs in a visualiserShow the approach
Scan every cell. Each time you find a 1, you have found a new island: add one to the count, then
flood-fill from that cell, visiting every land cell joined to it and setting each one to 0 so it
is never counted again. A stack of cells still to visit (depth-first) or a queue (breadth-first)
does the flood fill without recursion: pop a cell, and push each neighbour that is on the grid
and still land, sinking it as you push it.
Every cell is looked at a constant number of times. If you may not change the grid, keep a set of visited cells instead.
Time: O(rows · cols) · Space: O(rows · cols) for the stack in the worst case