Decoded

Number of Islands

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. You may assume all four edges of the grid are all surrounded by water.

Sample Input:

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

Expected Output: 1

Explanation: All '1's are connected horizontally or vertically, forming a single island.

Constraints

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

How We Solve This

  • Scan the grid cell by cell.
  • When we find an unvisited '1', we've discovered a new island.
  • Run DFS or BFS to explore all connected land cells from that point.
  • Mark the entire explored island as visited so it’s not counted again.
  • The number of times we start a DFS/BFS is the total number of islands.

Edge Cases to Consider

Empty Grid

Input: []
Output: 0

The algorithm should handle an empty grid and return 0.

All Water

Input: [["0","0","0"],["0","0","0"],["0","0","0"]]
Output: 0

There is no land at all, so there are 0 islands.

All Land

Input: [["1","1","1"],["1","1","1"],["1","1","1"]]
Output: 1

All land cells are connected, forming one big island.

Checkerboard Islands

Input: [["1","0","1"],["0","1","0"],["1","0","1"]]
Output: 5

Each '1' is isolated (no horizontal/vertical connection), so every land cell becomes its own island.