Given a 2-D grid of '1's (land) and '0's (water), count the number of islands (connected components of land).

How to think about it

The interviewer is checking whether you recognise a grid as a graph in disguise. The words “count the islands” are really “count the connected components,” and the moment you say that out loud you’ve shown you see the structure: each '1' is a node, and edges run to its four neighbours. Anyone can describe an island in plain English; the signal they want is that you’ll reach for flood fill rather than fumble with boundary-tracking.

The mechanism has two layers. The outer scan walks every cell. When it lands on a '1' that hasn’t been claimed, that’s the first cell of a brand-new island, so you bump the counter. Then you immediately flood-fill from that cell — a depth-first search that fans out to every connected land cell and marks it visited, either by flipping it to '0' or recording it in a set. By the time the flood returns, the entire island is consumed, so the outer scan never counts any of its cells again. The count therefore equals the number of times you started a new flood. Each cell is touched at most once by the scan and at most once by a flood, so the whole thing is linear in the grid size, O(m × n).

A worked example

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

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return                  # off-grid or water or already sunk
        grid[r][c] = '0'            # sink this land so it's never recounted
        dfs(r + 1, c)              # flood the four neighbours
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':   # a fresh island begins here
                count += 1
                dfs(r, c)           # consume the whole thing
    return count

grid1 = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1'],
]
print(num_islands(grid1))   # three separate land masses

grid2 = [['1','1','1'],['0','1','0'],['1','1','1']]
print(num_islands(grid2))   # all land, joined through the centre column

grid3 = [['0','0'],['0','0']]
print(num_islands(grid3))   # nothing but water

3
1
0

The first grid has three disjoint clumps of land, and three floods consume them, so the answer is 3. The second is the case that exposes a weak mental model: it looks like five separate blobs, but the centre cell bridges the top and bottom rows through 4-directional connectivity, so a single flood swallows everything and the count is 1. The third grid never enters the dfs, leaving the counter at 0.