Number of Islands

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is formed by horizontally or vertically adjacent land cells.

Function signature

func NumIslands(grid [][]byte) int

Inputs / outputs

• grid: matrix of bytes '0'/'1'.
• Return: number of islands.

Example

grid = [
  ["1","1","0","0"],
  ["1","1","0","0"],
  ["0","0","1","0"],
  ["0","0","0","1"],
]
Output: 3

Constraints

• 1 <= rows, cols <= 300

Core idea (near-solution)

Flood fill each unvisited land cell (DFS/BFS) and count how many times you start a new fill.

Invariant: once a cell is visited, it will not be counted again.

Algorithm (step-by-step)

1. Initialize count = 0.
2. For each cell:
   • If it is land and unvisited, increment count and flood fill to mark the whole island.
3. Return count.

Correctness sketch

• Invariant: once a cell is visited, it will not be counted again.
• DFS visits exactly all nodes reachable from a start node.
• Marking visited prevents revisits and guarantees termination.
• Repeating from unvisited nodes correctly handles all components.

Trace (hand walkthrough)

Example input:
grid = [
  ["1","1","0","0"],
  ["1","1","0","0"],
  ["0","0","1","0"],
  ["0","0","0","1"],
]
Output: 3

Walk:
- start at (0,0) -> flood fills 4 cells (top-left block), count=1
- next unvisited 1 at (2,2) -> count=2
- next unvisited 1 at (3,3) -> count=3

Pitfalls to avoid

• Forgetting to mark visited before recursing (causes infinite loops).
• Treating diagonal adjacency as connected (it is not).

Complexity

• Time: O(rows * cols).
• Extra space: O(rows * cols) for visited or recursion stack.

Implementation notes (Go)

• You can mutate the grid in-place by flipping '1' to '0' to mark visited.