Number of Islands

Learning goal: Translate the grid into a connected-components problem and identify what must be counted.

Core idea Every land cell belongs to exactly one island. The answer is therefore the number of connected components formed by land cells under four-directional movement. Water is not part of any component, and diagonal neighbors are deliberately ignored.

Algorithm plan

• Scan every coordinate from top to bottom and left to right.
• When the cell is water or already visited, continue.
• When the cell is fresh land, increment the island count.
• Flood-fill from that cell so the entire island becomes visited.

Micro-example In [["1","1"],["0","1"]], the first 1 launches one flood fill. Its three reachable land cells are one component, so the answer is 1.

Pitfalls

• Treating diagonal contact as connectivity changes the problem.
• Counting every land cell instead of every flood-fill launch overcounts.
• A visited representation must distinguish processed land from unprocessed land.

Recap

• Islands are four-directional connected components.
• Only an unvisited land cell starts a new component.
• One complete flood fill accounts for one island.

Learning goal: Understand why marking land immediately prevents recounting and infinite recursion.

Core idea Treat a visited land cell as if it has been sunk into water. Once a flood fill discovers a cell, mark it immediately before exploring its neighbors. Future scans and recursive calls then skip it, so the same island cannot launch another count and the traversal cannot loop back through already explored cells.

Flood-fill state

For a current cell (r, c), inspect:

• (r - 1, c) above
• (r + 1, c) below
• (r, c - 1) left
• (r, c + 1) right

A neighbor is explored only when it is inside the grid, still land, and unvisited. DFS uses the call stack; BFS uses an explicit queue. Both visit the same component and produce the same count.

Micro-example Starting at (0,0) reaches (0,1) and (1,0). Marking each as soon as it is enqueued or called ensures that neither is counted again later.

Pitfalls

• Marking after recursion allows duplicate pushes and repeated work.
• Forgetting bounds checks can access outside the grid.
• Reusing a land marker without deciding whether mutation is allowed can violate an input contract.

Recap

• Mark on discovery, not after all neighbors finish.
• DFS and BFS are equivalent component traversals.
• Sinking makes the invariant visible: discovered land is never revisited.

Learning goal: Write a correct scan-plus-flood-fill algorithm and recognize its invariant.

Core idea The outer scan is responsible for finding component representatives; the inner traversal is responsible for consuming one complete island. After processing any scan prefix, every land cell in that prefix is either already sunk or is the first cell of a flood fill currently being processed.

Algorithm plan

1. Set islands = 0.
2. For each cell (r, c), skip water and visited land.
3. For fresh land, increment islands and mark it visited.
4. Put it in a queue for BFS, or call dfs(r, c).
5. Repeatedly inspect four neighbors and mark each valid land neighbor immediately.
6. Return islands after the scan ends.

for each cell (r, c):
    if grid[r][c] == "1":
        islands += 1
        flood_fill(r, c)
return islands

Micro-example The first launch at (0,0) consumes three cells. The scan later reaches (1,3), which is still fresh, so it increments the count and consumes three more cells.

Pitfalls

• A DFS must have a base case for water, bounds, and visited cells.
• A BFS queue should mark cells when enqueued, not when dequeued.
• Do not start a second traversal from a cell consumed by the first one.

Recap

• The scan finds starts; flood fill consumes components.
• Immediate marking preserves the no-revisit invariant.
• BFS and DFS differ in order, not in correctness.

Learning goal: Trace one complete grid and see exactly when the island count changes.

Core idea Use the example [["1","1","0","0"],["1","0","0","1"],["0","0","1","1"],["0","0","0","0"]]. A scan encounters (0,0) first and flood-fills three connected cells. Later, (1,3) is the next unvisited land cell; its flood fill reaches (2,3) and (2,2). No other land remains unvisited, so the final count is two.

Traversal invariant

The visited set contains every land cell that has already been discovered. A cell enters visited before its neighbors are expanded. Thus each land cell is enqueued at most once, even when multiple island paths touch it.

Micro-example

• Launch 1: (0,0) → (0,1), (1,0).
• Launch 2: (1,3) → (2,3) → (2,2).

Pitfalls

• A diagonal-looking connection between (0,1) and (1,2) would still be water-separated.
• The count changes at launches, not at queue operations.

Recap

• The concrete grid has six land cells grouped into two components.
• The visualization follows the same example used in the problem statement.
• The final result is 2.

Learning goal: Diagnose the errors that make a connected-components solution overcount or fail to terminate.

Core idea The most important correctness rule is immediate marking. If a cell is not marked when discovered, neighboring calls can discover it again before the first call finishes. That can cause repeated work, recounting, or infinite recursion when two land cells point back to one another.

Defensive checks

A neighbor may be:

• Outside the grid.
• Water, represented by "0".
• Already visited.

A robust implementation handles all three before expanding. For recursive DFS, a very large one-cell-wide island can also create a deep call stack; iterative BFS or iterative DFS avoids language recursion limits.

Micro-example For adjacent land cells A and B, dfs(A) calls dfs(B). Without marking A first, dfs(B) can call dfs(A) again, creating a cycle of calls.

Pitfalls

• Accidentally allowing diagonal movement.
• Mutating the grid without documenting that choice.
• Forgetting that an all-water grid returns 0 and an all-land grid returns 1.

Recap

• Validate bounds and cell state before expansion.
• Mark before exploring neighbors.
• Consider iterative traversal for recursion-depth safety.

Learning goal: Connect flood fill to the disjoint-set model of connected components.

Core idea Instead of launching a traversal, assign each land cell to a set and merge neighboring land cells. Initially, every land cell is its own component. For each horizontal and vertical land pair, union() combines their roots; the number of successful merges decreases the component count.

Data structure model

• parent[x] points toward the representative of cell x.
• find(x) follows parent links and applies path compression.
• union(a, b) joins distinct roots, often using rank or size.
• Water cells are excluded from the component count.

Micro-example The six land cells in the walkthrough begin as six sets. Five adjacency links are enough to connect the cells into two groups, so the final number of components is 2.

Pitfalls

• Counting every root before all unions are complete can overcount.
• Unioning diagonal neighbors changes connectivity.
• Without path compression or union by rank, repeated operations can become slower.

Recap

• Union-Find is a valid alternative, not a different definition of an island.
• Both approaches process each cell and local adjacency a constant number of times.
• Flood fill is usually the clearest first solution for this grid problem.

Learning goal: Analyze the cost of flood fill and retain the reusable connected-components pattern.

Core idea Let R be the number of rows and C the number of columns. The scan examines every grid position once. During flood fill, each land cell is discovered at most once and has at most four neighbors checked, so traversal work is linear in the grid area.

Complexity

• Time: O(R · C).
• Space: O(R · C) in the worst case for the visited structure and queue, stack, or recursion depth.
• If the input grid may be mutated, changing visited land to water can reduce auxiliary visited storage, although the traversal frontier can still be O(R · C).

Micro-example For a 4 × 4 grid, the scan has 16 positions. The flood fills inspect each of the six land cells once, while constant-time neighbor checks account for the remaining local work.

Pitfalls

• Calling the algorithm O(number of islands) ignores the full-grid scan.
• Forgetting queue or recursion memory hides the worst-case space cost.
• A solution that revisits land can exceed linear time.

Recap

• Scan plus flood fill runs in O(R · C) time.
• Worst-case auxiliary space is O(R · C).
• The transferable pattern is: detect an unvisited component, count it, and consume it.