• m == grid.length, n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is the character '0' or '1'
• Cells touching only at a corner are not connected.
• The grid always has at least one cell, though it may be entirely water.

The word carrying all the weight here is connected. The grid does not tell you where the islands are; it tells you where the land is, and an island is whatever land happens to hang together. So the real question is how to group cells by connectivity, and then simply count the groups.

That structure — a graph split into separate clumps with no links between them — is called a set of connected components, and counting them is one of the most reusable tasks in all of graph work. The grid framing hides it, so it is worth naming: each land cell is a node, each pair of orthogonally adjacent land cells is an edge, and an island is exactly one connected component.

A first instinct is to give every land cell its own label, then repeatedly sweep the grid merging labels wherever two labelled cells touch, until a sweep changes nothing.

label = {}
next_id = 0
for r, c in all_cells:
    if grid[r][c] == '1':
        label[(r, c)] = next_id      # everyone starts in their own group
        next_id += 1

changed = True
while changed:                        # keep sweeping until labels settle
    changed = False
    for r, c in land_cells:
        for nr, nc in neighbours(r, c):
            if is_land(nr, nc) and label[(nr, nc)] != label[(r, c)]:
                # merge the two groups... and now what?
                changed = True

It is correct in spirit and painful in practice. Merging two labels means finding and rewriting every cell carrying the old label, and a long snaking island can require a fresh sweep for each link in the chain — so the sweeps multiply and the cost climbs toward O((m × n)²). Worse, the bookkeeping is genuinely fiddly, and fiddly bookkeeping under interview pressure is how bugs happen.

The waste is worth naming precisely: we are discovering connectivity in fragments and then repairing our earlier guesses. Each merge undoes a decision made before we had enough information.

Here is the shift. Rather than labelling everything and reconciling afterwards, walk the grid looking for land you have not seen before. The first time you touch a cell of some island, that island is brand new — so add one to the counter. Then, before continuing the scan, walk that entire island and mark every cell of it as seen, so that when the outer scan later passes over its other cells, they are no longer land as far as the scan is concerned.

Two loops, doing two completely different jobs:

No merging, no relabelling, no repeated sweeps. Each island is discovered once and erased once.

The inner traversal is naturally recursive, so it is worth being precise about what that means rather than waving at "a chain reaction".

A recursive function is one that solves a problem by handling a small piece itself and handing the rest to another copy of itself. Two things must be true or it never finishes:

Now the part people find uncomfortable. When sink(r, c) calls sink(r+1, c), do not attempt to trace where that call goes. Assume it does its job — it will sink everything reachable from below and return. This is not hand-waving; it is an induction argument. The base case is correct by inspection, and if every call on a smaller amount of land is correct, then a call that sinks its own cell and delegates the four directions is correct too. So every call is correct.

Mechanically, each in-progress call gets a stack frame holding its local values and the point to resume at. The frames pile up while the traversal descends and unwind as calls return. That pile is why a 90,000-cell island can exhaust the interpreter's stack — the recursion is 90,000 frames deep at its worst.

def num_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return                       # base case: off-grid or not land
        grid[r][c] = '0'                 # mark BEFORE recursing
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':        # untouched land: a new island
                count += 1
                sink(r, c)
    return count

The code has a doubly nested loop with a traversal inside it, which looks expensive, but it is linear and the reason is worth being able to state.

Count how often each cell is touched. The outer scan visits every cell exactly once. The inner traversal only ever enters a cell that is currently land, and it immediately converts it to water, so no cell can be entered by a traversal more than once. Each cell therefore costs a constant amount of work overall, and the total is O(m × n) time.

Space is the recursion depth: O(m × n) in the worst case, a single island snaking through every cell.

Grid:

1 1 0
1 0 1
0 1 1

The scan proceeds left to right, top to bottom.

Answer 2. Notice (1,0) and (2,1) look close on the page but are diagonal to each other, and no route of horizontal and vertical steps joins them — which is why this is two islands and not one.

Strip away the islands and a shape remains that recurs constantly: scan for an unvisited node, count it, then consume its whole component. Filling it in for a new problem means answering three questions.

Recognition signals: the words how many groups, how many regions, number of connected components, number of provinces, count the clusters. Any question about how many separate clumps exist is this pattern, whether the input is a grid, a friendship matrix, or a list of edges.

Depth-first search is the natural fit because the question asks nothing about distance. Breadth-first search with a queue would visit exactly the same cells and give exactly the same count — the choice only matters when the answer depends on how far apart things are. DFS is shorter to write; BFS avoids the deep recursion, which on a 300 × 300 grid is a genuine concern rather than a theoretical one.

There is a third route worth naming since interviewers ask for it: union-find, a structure that keeps a representative for each group and merges two groups in near-constant time. It rescues the failed first approach by making merging cheap instead of catastrophic, and it is the right tool when land is added over time and the count must be reported after each addition — a traversal from scratch on every update would be far too slow.

Train the reflex: whenever a question asks how many separate groups exist, do not try to merge things as you go. Find one unvisited member, claim its entire group, and count how many times you had to start over.