Number of Islands

Medium·Tagsgraphdfsbfsmatrix

Problem Statement

Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically (4-directionally). You may assume all four edges of the grid are all 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"]
]

Grid

Output

"1"

Why

Every land cell touches another land cell above, below, left, or right, so they all form one connected piece of land. That single island makes the count 1.

Example 2

Input

grid: [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Grid

Output

"3"

Why

There is a 2x2 island in the top left, a single '1' island in the middle, and a 1x2 island in the bottom right.

Constraints

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

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

Treat the 2D grid as an undirected graph where each '1' is a vertex, and edges connect adjacent '1's horizontally and vertically.

Hint 2

Iterate through the grid using a nested loop. Whenever you find a '1', you have found a new island! Increment your island counter.

Hint 3

But how do you prevent counting the same island multiple times? You need to 'sink' it! When you find a '1', trigger a Depth-First Search (DFS) or Breadth-First Search (BFS) to visit all connected '1's and flip them to '0's.

Hint 4

Once the DFS/BFS completes, the entire island has been wiped from the map, ensuring that the nested loops won't double-count any of its parts.