Number of Islands (Plain and Streaming)

Requirements

• Input: a two-dimensional array whose entries are the string values '1' for land and '0' for water.
• Output: return how many islands exist. An island is one connected land region using only up, down, left, and right neighbors; diagonal contact does not connect regions. Treat everything beyond the grid boundary as water.
• Constraints: 1 <= grid.length, grid[i].length <= 100.

def numIslands(grid: list[list[str]]) -> int:...
    # Produces the number of land regions connected in the four cardinal directions.
    # Each region contains every horizontally or vertically neighboring '1' cell reachable from it.

• Frequently seen variations:
  • Rotting oranges / infection propagation (LC 994 terminology) — compute BFS rounds rather than the number of components.
  • Incremental islands (LC 305) — handle a sequence of addLand updates and report the island total after every update (described in the alternate standard version below).

Notes

• A typical extension asks: "How would you handle a grid that cannot fit in memory?"
• In a senior-level phone screen, a likely extension is: "after each addLand, return the largest island size."
• Some interviewers require union-find for the ordinary LC 200 version specifically to assess familiarity with that data structure, even when DFS handles the main task.

Alternate canonical variant — incremental updates (Number of Islands II)

Begin with an m x n board containing only water. Every addLand operation changes one location into land, and you must give the current number of islands immediately after each update.

# Streaming inputs are m: int, n: int, and positions: list[list[int]].
# positions[i] = [ri, ci] changes (ri, ci) to land during operation i.
# Return a list whose i-th value is the four-directional island count after operation i.
# The returned list has len(positions) entries, representing live counts rather than only the ending total.

• Return behavior: emit exactly one result for each update, preserving update order; one insertion may therefore combine multiple islands and reduce the total.
• Constraints: 1 <= m, n <= 10^4, 1 <= m * n <= 10^4, 0 <= positions.length <= 10^4, 0 <= ri < m, 0 <= ci < n. positions is allowed to be empty, in which case return []. A coordinate can also occur repeatedly; adding land where land already exists does not alter the count.

Preparation

• Practice LC 200, LC 305, and LC 994 together because their central traversal ideas overlap.
• Be able to write a union-find implementation with parent, rank, and size arrays without reference material.
• Prepare an explanation for the "largest island after every addLand" extension; it has been a decisive senior-interview variation in several loops.