Number of Islands
You get a grid of numbers where 1 means land and 0 means water. An island is a group of land cells connected up, down, left or right (diagonal cells do not connect).
Return the number of islands in the grid. You may assume everything outside the grid is water.
Examples
Green cells are land (1) and blue cells are water (0).
Input grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]
Output 3
Green cells are land (1) and blue cells are water (0).
Input grid = [[1,1,1],[0,1,0],[1,1,1]]
Output 1
Everything connects through the middle.
Green cells are land (1) and blue cells are water (0).
Input grid = [[0,0],[0,0]]
Output 0
Constraints
- 1 <= rows, columns <= 300
- Each cell is 0 or 1
Stuck? Take one hint at a time
Common mistakes
- Counting every land cell instead of every connected group.
- Forgetting to mark cells as visited, which loops forever or counts islands many times.
- Marking cells when you pop them from the stack instead of when you push them, which lets the same cell be pushed many times.
- Letting neighbor checks run past the edges of the grid.
Questions an interviewer may ask next
- Do it without changing the input grid. (Use a separate visited set.)
- Return the size of the largest island.
- Count islands when diagonal cells also connect.
- The grid is huge and arrives in chunks. What structure fits? (Union-find.)
How often this is reported
Commonly reported across 19 of 25 tracked companies
19/25
Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.
grid
[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]
Expected output
3
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.