Count Islands in a Grid

Problem Given a 2D grid of land (1) and water (0) cells, count the number of islands — maximal groups of land cells connected to each other. The question is framed as a graph-traversal deep-dive, so expect to be pushed on why DFS or BFS is the right choice and where each breaks down.

Input / Output

• Input: a 2D grid of 0/1 cells (equivalently, a graph as an adjacency list).
• Output: the number of connected components of land cells.

Constraints

• Up to ~10^4–10^5 cells or nodes.
• Adjacency is 4-directional (up/down/left/right) unless stated otherwise — worth confirming, since 8-directional changes the answer.
• The grid may be modified in place, or may not be, which decides whether a separate visited set is needed.

Example

• Grid [[1,1,0],[0,1,0],[0,0,1]] → 2: the connected land mass in the top-left, and the isolated cell at the bottom-right.
• Tricky cases: an all-water grid → 0; an all-land grid → 1; and two land cells touching only diagonally, which count as 2 under 4-directional adjacency but 1 under 8-directional.