Number of Islands

Problem

Given an m × n 2D binary grid where '1' is land and '0' is water, return the number of islands. An island is a group of adjacent '1's connected horizontally or vertically. Assume all edges are surrounded by water.

Example: [["1","1","0"],["0","1","0"],["0","0","1"]] → 2 islands.

What the interviewer is testing

• Can you recognize this as a connected-components problem?
• Do you correctly handle grid boundaries in your DFS/BFS?
• Do you use in-place marking (or a visited set) to avoid infinite loops?

DFS solution — O(m·n) time, O(m·n) worst-case stack

Scan the grid. When you find a '1', increment the count and flood-fill all connected land to '0' so we don't count them again.

def num_islands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return
        grid[r][c] = '0'                # mark visited in place
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

BFS variant — same complexity, no stack overflow risk

On grids with a huge single island (say 1000×1000 all-1), the DFS stack can blow up. BFS with a queue keeps the frontier bounded by the perimeter.

from collections import deque

def num_islands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] != '1':
                continue
            count += 1
            q = deque([(r, c)])
            grid[r][c] = '0'
            while q:
                x, y = q.popleft()
                for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                        grid[nx][ny] = '0'
                        q.append((nx, ny))
    return count

Complexity — what to say out loud

"Time O(m · n) — every cell visited a constant number of times. Space O(m · n) worst case for the DFS stack or BFS queue on a fully-connected grid. Mutating the grid in place avoids a separate visited set."

Edge cases the interviewer will ask about

• Empty grid — return 0. Early exit.
• All water — return 0. Outer loop finds no '1'.
• All land — return 1. One flood-fill.
• Diagonal adjacency — clarify with the interviewer; this problem uses 4-directional only.

Common follow-ups

• "Number of distinct island shapes." — During DFS, record the trajectory of moves relative to a start point; normalize; count unique.
• "Largest island area." — Return the size of each DFS/BFS traversal, take the max.
• "Islands with the ability to change one water to land." — Precompute area of each island via Union-Find, then for each water cell sum the areas of neighboring islands (deduped).
• "Streaming version — cells arrive one at a time." — Classic Union-Find (Number of Islands II).

How to verbalize your answer

"This is connected components on a grid. Scan cell by cell. When I find land, increment the count and flood-fill everything reachable to water so I don't recount it. DFS is clean but I can also do BFS if the grid might be huge and I want to avoid stack overflow. Time O(m·n), space O(m·n) worst case."