Number of Islands

Difficulty: Medium

Problem

A map is stored as a grid of characters, '1' for land and '0' for water. Return how many separate islands it contains. Two land cells belong to the same island when you can walk between them by stepping up, down, left, or right over land only. Cells that merely touch at a corner are NOT joined, and you may assume everything beyond the grid's border is water.

Example

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
Explanation: Three separate pieces of land: the 2×2 block in the top-left, the lone cell at (2,2), and the pair (3,3)–(3,4). The cell at (2,2) touches the block and the pair only at corners, and corners don't join, so it is an island of its own.

Brute-force approach

There is no separate brute force worth writing, scan-and-flood IS the natural solution. (The true 'brute force', exploring from every land cell without marking anything, just recounts the same island over and over.)

Optimal approach

Key insight: The scan finds each island exactly once; the flood erases it so it can never be found again. Count the finds.

Walk every cell of the grid in reading order. Each time you step on land that hasn't been sunk yet, that's a brand-new island: count it, then flood-sink every cell of it so the scan can never count it again.

Steps

Scan the grid row by row, left to right
On unsunk land ('1'): a never-before-seen island, count += 1
Immediately sink(r, c): DFS in all 4 directions, flipping every cell of the island to '0'
Sunk cells fail the '1' check later, so the scan glides right past them
When the scan finishes, count is the answer

Time complexity: O(rows × cols) · Space complexity: O(rows × cols) worst-case recursion

Pseudocode

function numIslands(grid):
    count = 0
    
    function sink(r, c):
        if out_of_bounds(r, c) or grid[r][c] != ____:
            return
        grid[r][c] = ____
        sink(r-1, c); sink(r+1, c)
        sink(r, c-1); sink(r, c+1)
    
    for r in 0 .. rows-1:
        for c in 0 .. cols-1:
            if grid[r][c] == '1':
                count = count + ____
                ____(r, c)
    
    return count

Hints

The flood must stop on anything that isn't fresh land, ocean AND already-sunk cells both. Which character marks fresh land?
Sinking turns land into water so it can never look new again. What value drowns the cell?
The scan just found land no flood has claimed, a whole new island. How much does the count grow?
Right after counting, which function must erase ALL of the island's cells before the scan takes another step?

Complexity questions

The grid has m rows and n columns. Counting the scan AND all the floods together, what is the total time?

O(m × n): the scan touches each cell once, and each cell is sunk at most once across ALL floods combined. The floods look expensive, but add up their work over the ENTIRE run: a cell can only be sunk once ever, because sinking makes it fail the '1' check forever after. So the scan does m×n checks, and all floods together do at most m×n sinks, O(m × n) total.

Worst case for the recursive sink: what island shape hurts, and how deep can the call stack go?

One giant snake island winding through every cell. The stack can reach O(m × n) frames deep. Picture a single serpentine island threading through all m×n cells: sink calls sink calls sink, one frame per cell, before anything returns, O(m × n) deep, enough to blow Python's default recursion limit on big grids. An iterative flood (explicit stack, or a BFS queue) does the identical job without deep recursion.

Your interviewer adds a rule: the grid must NOT be modified. What changes?

Keep a separate visited set or boolean matrix. O(m × n) extra memory; sinking was a space optimization, not a requirement. Only the MARKING moves: instead of flipping cells to '0', add (r, c) to a visited set (or flip a boolean matrix), and have the flood skip visited cells. The scan-and-flood logic is untouched. Sinking earns you O(1) extra space, but a visited set at O(m × n) is the polite version when the input is sacred.

New problem: 'count the friend circles, given an n×n adjacency matrix of who knows whom.' Same pattern?

Yes: scan the people, and each unvisited person starts a new circle: count it, flood everyone reachable, repeat. It's connected components in yet another costume: people are nodes, friendships are edges. Scan person by person; on someone no flood has claimed, count += 1 and DFS their whole circle via the matrix row. The only difference from islands is where neighbors come from: a matrix row instead of 4 grid directions.

Check your understanding of Number of Islands

What exactly counts as ONE island?

A maximal group of '1's connected up/down/left/right. The whole clump is one island. An island is the whole connected clump: stand on any land cell and walk up/down/left/right over land, everything you can reach is the SAME island. In the example, (0,0), (0,1), (1,0), and (1,1) are four cells but only ONE island.

Recognize the costume: which Graph Foundations pattern is this problem secretly wearing?

Counting connected components: scan for an unvisited piece, flood it, repeat. This is literally 'count the components' on a grid graph: cells are nodes, and each cell has edges to its 4 neighbors. From foundations you know the recipe. Scan all nodes, and every time you find one no flood has claimed yet, that's a new component: count it and flood it.

When the flood claims an island, why do we SINK every one of its cells (flip '1' → '0')?

It's the in-place visited marker: the scan will pass those cells later and must NOT count them as new islands. The scan doesn't stop after a discovery. It keeps marching over every remaining cell, including the rest of the island we just counted. Sinking those cells first means they read as '0' when the scan arrives, so the counter never ticks twice for one island. It's Flood Fill's in-place marking trick, reused.

Trace the example: scanning row by row, left to right, the scan first hits land at (0,0). What does the flood sink before the scan takes another step?

All four cells of the 2×2 top-left block: (0,0), (0,1), (1,0), (1,1). sink(0,0) drowns (0,0), then spreads to its land neighbors: right to (0,1), down to (1,0), and on to (1,1), the whole first island, and nothing beyond it, because water blocks the flood. When the scan later reaches (0,1), (1,0), and (1,1), they're already '0' and get skipped.

The diagonal trap: is [["1","0"],["0","1"]] one island or two?

Two: diagonal touching is NOT connectivity here; only up/down/left/right count. Connectivity is strictly 4-directional. From (0,0) the only neighbors are (0,1) and (1,0), both water, so the flood stops after one cell, and (1,1) later starts its own island. Answer: two. Interviewers love slipping this in, so nail it down now.