Number of Islands

Medium~20 min

Given an m x n 2D grid where 1 represents land and 0 represents water, return the number of islands.

An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Examples

Example 1

Input:

grid = [
  [1, 1, 1, 1, 0],
  [1, 1, 0, 1, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 0, 0]
]

Output: 1

Explanation: All the land cells are connected, forming one island.

Example 2

Input:

grid = [
  [1, 1, 0, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 1, 1]
]

Output: 3

Explanation: There are three separate groups of connected land cells, so there are three islands.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is 0 or 1
Expected time complexity: O(m × n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run