Count the islands in a grid
DSA, Medium
Which structure or algorithm, and what does it cost.
You get a grid of the characters "1" (land) and "0" (water). Two land cells are connected if they share an edge (up, down, left or right). Diagonal cells are not connected. An island is a group of connected land cells. Return the number of islands. An empty grid has 0 islands.
Examples
Input 11000
11000
00100
00011
Output 3
Why top-left block, the single cell in the middle, the bottom-right pair
Input 10
01
Output 2
Why the two 1s touch only on a corner, so they are separate islands
Input 000
Output 0
Why no land
Constraints
- 0 <= rows, columns <= 1,000. The grid may have up to 1,000,000 cells.
- Each cell is
"0"or"1". - The input may be changed.
Your answer must contain
- The method; code; time and memory; a hand trace of example 1; what goes wrong with DFS recursion on a 1000 x 1000 grid of all land and what you do about it.