Graphs Grids as graphs
435. Number of Islands
You are given a map as a grid of integers, grid, with m rows and n columns. A cell that holds 1 is
land, and a cell that holds 0 is water.
An island is a group of land cells joined by steps up, down, left or right. Two land cells that touch only at a corner are not joined. Everything outside the grid is water.
Return the number of islands.
Example 1
Input: grid = [[1, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 1, 0, 0],
[0, 1, 1, 0, 1]]
4Explanation: The islands are the three cells in the top-left corner, the three in the top-right corner, the three at the bottom in the middle, and the single cell in the bottom-right corner. The land at row 2, column 2 touches the top-right island only at a corner, so it is not part of it.
Example 2
Input: grid = [[0, 0, 0], [0, 0, 0]]
0Explanation: There is no land, so there are no islands.
Example 3
Input: grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
1Explanation: The eight land cells form one ring, so they are one island. The water in the middle does not split it.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
m == grid.length,n == grid[i].length1 ≤ m, n ≤ 300grid[i][j]is 0 or 1.
Clarifying questions
What you would ask an interviewer before writing any code.