Number of Islands (Making an Island)

Problem Statement

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is a group of '1's connected horizontally or vertically (not diagonally). The grid is surrounded by water on all edges.

Constraints

• 1 <= grid.length, grid[0].length <= 300
• Each cell is '0' or '1'

Example

Input:

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

Output: 3

Explanation: Top-left 2x2 block is one island, the single 1 in the middle is another, and the bottom-right 1 is the third.

What the Interviewer Expects

1. Multiple valid approaches — DFS, BFS, or Union-Find (DSU). Know at least two.
2. DFS/BFS flood fill — iterate every cell. When you hit an unvisited '1', increment count and flood-fill all connected land (mark visited).
3. Union-Find alternative — union adjacent land cells, count distinct roots at the end.
4. Mark visited — either mutate the grid (set to '0') or use a visited set.
5. Time: O(rows × cols), Space: O(rows × cols) worst case for recursion/queue.

Follow-ups

1. What if the grid is too large to fit in memory? How would you process it?
2. What if diagonal connections also count?
3. How would you find the size of the largest island?
4. Follow-up: "Making a Large Island" — if you can flip one 0 to 1, what's the max island size you can create?
5. When would DSU be preferred over DFS/BFS for this problem?