Number of Islands
MediumGraphs · Amazon · Google · NVIDIA
You are given an m x n grid where each cell is the string "1" (land) or "0" (water). An island is a group of land cells connected horizontally or vertically; cells that touch only at a corner are not connected. Everything outside the grid is water.
Return the number of islands. You may modify grid while solving.
Example 1
- Input:
- grid = [["1", "1", "0", "0", "1"], ["1", "0", "0", "1", "1"], ["0", "0", "1", "0", "0"], ["1", "0", "0", "0", "1"]]
- Output:
- 5
- Explanation
- The islands are the three cells in the top-left corner, the three cells in the top-right corner, the single cell in the centre, and the single cells in the two bottom corners: 5 in total. The centre cell touches nothing horizontally or vertically.
Example 2
- Input:
- grid = [["1", "0", "1", "1"]]
- Output:
- 2
- Explanation
- The water cell splits the row into a single cell on the left and a pair on the right.
Example 3
- Input:
- grid = [["0", "0"], ["0", "0"]]
- Output:
- 0
- Explanation
- There is no land, so there are no islands.
Constraints
m == grid.length,n == grid[i].length1 <= m, n <= 300grid[i][j]is"0"or"1"