noodleProblems/
Number of Islands
#145

Number of Islands

AlgorithmmediumArrayDepth First SearchBreadth First SearchUnion FindMatrix

You are given an m x n grid where each cell is either "1" (land) or "0" (water), as a 2-D array of single-character **strings**.

An **island** is a maximal group of "1" cells joined **4-directionally** (up, down, left, right — *not* diagonally), bounded by water or the edge of the grid. Assume the grid is surrounded by water on all sides.

Return the number of distinct islands.

Example cases

  • one big island
    in grid =
    11110
    11010
    11000
    00000
    out 1
    All the land cells are connected horizontally or vertically into a single component.
  • three islands
    in grid =
    11000
    11000
    00100
    00011
    out 3
    The top-left 2x2 block, the lone cell in the middle, and the bottom-right pair are three separate islands.
  • single water cell
    in grid =
    0
    out 0

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is "0" or "1".
Saved
grid =
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]