Number of Islands

Statement

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is a maximal group of horizontally or vertically connected land cells. The grid's boundary is implicitly water.

Examples

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

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

Constraints

• 1 ≤ m, n ≤ 300
• grid[i][j] is either '0' or '1'.
• Connectivity is 4-directional (up, down, left, right), not diagonal.

What this problem is really testing

Whether you can recognise an unmarked-graph problem and pick the right traversal. The grid is an implicit graph, each cell is a node, with edges to its four neighbours. Iterating over cells, launching DFS or BFS from each unvisited land cell, and counting launches is the canonical pattern. The choice of DFS vs BFS is secondary; both work, both are O(m × n).