📖 11 min read
Last updated on

Number of Islands — Coding Interview Walkthrough

By intervu.dev

Hero Image for Number Of Islands

You’re in a coding interview. The interviewer says: “Given a 2D grid of ‘0’s and ‘1’s, count the number of islands.” You know this is a graph traversal problem. You know DFS. But now you need to explain why the grid is an implicit graph, justify your choice between DFS and BFS, handle the in-place mutation tradeoff, and reason about complexity on a 2D input while someone watches you navigate boundary conditions.

This walkthrough covers the complete arc: grid-as-graph modeling, two full implementations (DFS and BFS), the tradeoffs between them, every edge case worth mentioning, and a model of what a polished interview performance sounds like.

The Problem

You are given an m x n grid of characters where '1' represents land and '0' represents water. An island is defined as a group of adjacent land cells connected horizontally or vertically (not diagonally). Return the total number of islands in the grid. (LeetCode #200)

Example

Input

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1", "medium"]
, "medium"]

Output 3

The first island is the 2x2 block of '1's in the top-left. The second is the single '1' in the middle. The third is the two connected '1's in the bottom-right. Cells are only considered connected if they share an edge, diagonal adjacency doesn’t count. Counting islands correctly requires both finding unvisited land cells and fully exploring (and marking) each connected component before moving on.

Already comfortable with the solution? Practice it in a mock interview →

4×5 grid with three color-coded islands: green 2×2 block (top-left), amber single cell (center), and blue pair (bottom-right).

What Interviewers Are Actually Testing

Number of Islands is a connected-components problem dressed in a grid. Interviewers use it to assess how naturally you think in terms of graph traversal and whether you can implement it precisely on a 2D structure rather than an explicit adjacency list.

SkillWhat Interviewers Observe
Graph modelingDo you recognize the grid as an implicit graph with 4-directional edges?
DFS vs. BFS decisionCan you choose between the two and justify the tradeoff?
Visited trackingDo you mark cells in-place or use a separate visited set, and can you explain why?
Boundary checkingDo you correctly guard against out-of-bounds and water cells before recursing?
Complexity on gridsCan you express O(m x n) time and space clearly for a 2D input?
Follow-up readinessCan you extend to max island size, island perimeter, or number of distinct shapes?

Step 1: Clarifying Questions

Before coding, taking a moment to ask smart questions frames the entire solution and prevents building the wrong thing. Here are the most important ones for Number of Islands:

  1. Are cells connected only horizontally and vertically, or also diagonally? The problem specifies 4-directional connectivity: up, down, left, right only. Confirming this prevents implementing an 8-directional traversal that would merge islands that shouldn’t be merged. It’s a detail that visually looks minor but changes the answer.

  2. Can I modify the input grid, or do I need to preserve it? Modifying cells in-place (marking visited '1's as '0's) is the simplest visited-tracking approach and avoids allocating a separate visited set. Confirming whether mutation is acceptable shapes your implementation choice immediately.

  3. What should I return if the grid is empty? An empty grid or a grid of all '0's should return 0. Confirming this keeps your base case logic clean.

  4. Are the grid values characters ('0'/'1') or integers (0/1)? LeetCode uses character strings. This affects your comparison operators: cell == '1' not cell == 1. A subtle type mismatch causes incorrect results that are hard to debug under pressure.

  5. What are the grid size constraints? LeetCode allows grids up to 300x300, meaning up to 90,000 cells. This rules out any approach worse than O(m x n) and confirms that DFS with Python’s default recursion limit may need attention for very large grids, worth mentioning proactively.

Step 2: A First (Non-Optimal) Idea

A naive approach might scan the grid repeatedly, merging cells into islands on each pass until no further merges are possible. Each pass checks every pair of adjacent cells, which means revisiting the entire grid O(k) times where k is the number of islands. Even a single-pass approach that doesn’t mark visited cells would recount the same land cells across multiple starting points, producing an inflated count.

The core inefficiency is revisiting cells. Without a visited mechanism, every '1' cell triggers a new traversal that re-explores cells already counted. For a dense grid, this balloons to O((m x n)^2) in the worst case.

ApproachTimeSpace
Repeated scanning (no visited)O((m x n)^2)O(1)
DFS/BFS with visited markingO(m x n)O(m x n)

The key realization is that each cell only needs to be visited once. A connected-component traversal that marks cells as it goes processes each cell exactly once across all traversals. That’s the insight that makes DFS and BFS the right tools here.

Step 3: The Key Insight

Treat each unvisited '1' cell as the starting point of a new island, and immediately “sink” the entire island by marking all connected land cells as visited before moving on.

Here’s the mental model that makes Number of Islands click:

As you scan the grid left-to-right, top-to-bottom, every time you land on an unvisited '1':

  • Increment your island counter by 1.
  • Launch a DFS (or BFS) from that cell.
  • During the traversal, mark every reachable land cell as visited, either by changing '1' to '0' in-place, or recording it in a visited set.
  • When the traversal completes, every cell of that island has been processed and won’t be counted again.

Continue scanning. The next unvisited '1' you encounter must belong to a different island. Increment again and repeat.

By the time you’ve scanned the entire grid, your counter holds the exact number of distinct islands. Each cell is visited at most once across all traversals, giving O(m x n) total time.

The choice between DFS and BFS is mostly stylistic for this problem. Both are correct and have the same asymptotic complexity. DFS is more concise to write recursively. BFS avoids potential stack overflow on very large grids. Knowing both and being able to articulate the tradeoff is a strong signal.

Step 4: Optimal Strategy

Here’s the DFS-based algorithm, step by step:

  1. Initialize island_count = 0.
  2. Get grid dimensions: rows = len(grid), cols = len(grid[0]).
  3. Define a helper dfs(r, c) that:
    • Returns immediately if r or c is out of bounds, or grid[r][c] != '1'.
    • Marks grid[r][c] = '0' to sink the cell and prevent revisiting.
    • Recursively calls dfs on all four neighbors: up, down, left, right.
  4. Iterate over every cell (r, c) in the grid.
  5. When grid[r][c] == '1' is found, increment island_count and call dfs(r, c) to sink the entire island.
  6. Return island_count.

Python Implementation

DFS (Recursive): Clean and Concise

def numIslands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    island_count = 0

    def dfs(r, c):
        # Base case: out of bounds or not land — stop exploring
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return

        grid[r][c] = '0'  # Sink the cell — mark as visited in-place

        # Explore all 4 neighbors
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                island_count += 1  # Found a new island
                dfs(r, c)          # Sink the entire island

    return island_count

BFS (Iterative): Stack-Safe for Large Grids

from collections import deque

def numIslands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    island_count = 0

    def bfs(r, c):
        queue = deque([(r, c)])
        grid[r][c] = '0'  # Mark as visited immediately upon enqueuing

        while queue:
            row, col = queue.popleft()
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    grid[nr][nc] = '0'  # Mark before enqueuing to avoid duplicates
                    queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                island_count += 1
                bfs(r, c)

    return island_count

Key implementation notes worth calling out in an interview:

  • In the BFS version, mark cells as '0' when enqueuing, not when dequeuing. Marking on dequeue allows the same cell to be enqueued multiple times from different neighbors, causing duplicate processing. Marking on enqueue prevents this.
  • The DFS approach modifies the input grid. If the interviewer says the grid must be preserved, use a separate visited = set() instead and check (r, c) not in visited before exploring.
  • The [(1,0),(-1,0),(0,1),(0,-1)] direction list is a reusable pattern across all grid traversal problems, worth memorizing as a convention.
  • For very large grids, the recursive DFS may hit Python’s default recursion limit. Mentioning this and offering BFS as the stack-safe alternative demonstrates production-level awareness.

Time & Space Complexity

OperationComplexity
TimeO(m x n)
SpaceO(m x n)

Time: Every cell in the grid is visited at most once, either during the outer scan or during a DFS/BFS traversal. Each visit does a constant amount of work. Total: O(m x n).

Space: In the worst case (a grid entirely of '1's), the DFS recursion stack can reach O(m x n) depth, or the BFS queue can hold O(m x n) entries. If a separate visited set is used instead of in-place marking, space remains O(m x n).

A common interviewer follow-up: “Can you reduce space?” The in-place marking approach uses no extra memory beyond the call stack. The stack itself is bounded by O(m x n) in the worst case, and there’s no general way to avoid this for graph traversal. Be honest about this rather than over-claiming.

Common Interview Mistakes

  1. Checking bounds after the recursive call rather than before. In recursive DFS, always validate r, c, and grid[r][c] at the top of the function, returning early if invalid. Checking after causes an IndexError before the guard ever fires.

  2. Marking cells as visited after exploring neighbors instead of immediately. Whether using DFS or BFS, mark a cell the moment you decide to process it, not after. Delayed marking allows the same cell to be enqueued or recursed into multiple times, inflating the count.

  3. Including diagonal neighbors. The problem specifies 4-directional connectivity. Including diagonals (8 directions) merges islands that should remain separate. Always confirm connectivity rules before coding.

  4. Forgetting the empty grid guard. if not grid or not grid[0] handles both a completely empty list and a list of empty rows. Missing this causes an IndexError on grid[0] before the traversal even begins.

  5. Not mentioning the input mutation tradeoff. Modifying the input grid is convenient but destructive. Always flag this explicitly: “I’m modifying the grid in-place, is that acceptable?” Proposing a visited set as an alternative shows you’ve thought about both approaches.

  6. Confusing rows and columns in bounds checks. The condition is 0 <= r < rows and 0 <= c < cols. Rows bound r, columns bound c. Swapping them produces subtle bugs that only surface on non-square grids.

  7. Not narrating the graph modeling step. Candidates who jump straight to “I’ll do DFS” without explaining that the grid is an implicit graph where adjacent '1's are connected nodes miss the most important conceptual moment. Always articulate the abstraction before the code.

What a Strong Candidate Sounds Like

“I’m looking at this as a graph problem. Each '1' cell is a node, and edges exist between horizontally or vertically adjacent '1's. I need to count connected components.

My approach: scan every cell. When I find an unvisited '1', I’ve found a new island. I increment my counter and immediately DFS to mark every cell in that island as visited by sinking it to '0'. By the time DFS returns, the entire island is processed and won’t be counted again.

I’ll mark cells in-place to avoid allocating a separate visited set. I should confirm that mutating the input is acceptable. Time is O(m x n) since every cell is visited at most once. Space is O(m x n) for the recursion stack in the worst case. If stack depth is a concern on very large grids, I can use BFS with an explicit queue instead. Let me code the DFS version and trace through the example.”

Example Interview Dialogue

Interviewer: Count the number of islands in a grid of '0's and '1's.

Candidate: Before I start: are cells connected only in 4 directions, or also diagonally? And can I modify the grid in-place?

Interviewer: Four directions only. You can modify the grid.

Candidate: Perfect. I’ll treat this as a connected-components problem. For each unvisited '1', I’ll increment my count and DFS to sink the entire island by marking cells '0' as I go. That way I never double-count.

Interviewer: What’s the time complexity?

Candidate: O(m x n). Every cell is visited at most once across all DFS calls. The outer scan is O(m x n), and the total work inside all DFS calls combined is also O(m x n) since no cell is processed twice. Space is O(m x n) for the recursion stack in the worst case: a fully-land grid would cause a single DFS to recurse m x n levels deep.

Interviewer: What if you couldn’t modify the grid?

Candidate: I’d use a visited set of (r, c) tuples. Before recursing into a neighbor, I’d check it’s not already in visited and add it on entry. Same O(m x n) time and space, just explicit instead of in-place.

Interviewer: How would you find the size of the largest island instead?

Candidate: Instead of incrementing a global counter, I’d have each DFS return the number of cells it visited. I’d return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1) from each call, and track the maximum return value across all top-level DFS invocations. Same traversal, different aggregation.

Number of Islands is the entry point to a large family of grid graph problems. These all use the same DFS/BFS-on-a-grid pattern with progressively richer constraints:

  • Max Area of Island (LeetCode #695). Same DFS structure, return the cell count of the largest island instead of total island count.
  • Island Perimeter (LeetCode #463). No DFS needed. Count boundary edges of land cells, a clever counting-based variant.
  • Surrounded Regions (LeetCode #130). Reverse the logic: BFS from boundary 'O's to find which regions are not surrounded.
  • Rotting Oranges (LeetCode #994). Multi-source BFS from all initially rotten cells simultaneously. Tests BFS level-by-level thinking.
  • Pacific Atlantic Water Flow (LeetCode #417). Reverse-flow BFS from both ocean boundaries. Tests bidirectional graph reasoning on grids.

The jump from Number of Islands to Max Area of Island (#695) is the most common interview escalation. It requires only a small change to the DFS return value but tests whether you understand the traversal deeply enough to modify it on the fly.

Practice This in a Mock Interview

This walkthrough gives you the complete framework: grid-as-graph modeling, DFS vs. BFS tradeoffs, in-place vs. visited-set tracking, and complexity analysis on 2D inputs. But grid traversal problems have a specific failure pattern in live interviews. Candidates who understood every piece of the solution still produce buggy code when bounds-checking under pressure, or mark cells at the wrong moment and end up with an infinite loop or inflated count.

The boundary condition r < 0 or r >= rows or c < 0 or c >= cols looks trivial written calmly. Under a ticking clock with someone watching, it’s exactly where the errors hide. Repetition under realistic conditions is the only way to make it automatic.

Start a mock interview for Number of Islands on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →