Young Devs Bin
🧮 Algorithm

Breaking Down Number of Islands

·4 min read·#algorithm#bfs#dfs#graph#leetcode

Number of Islands is one of the most frequently asked interview problems — open the Companies tab and you'll see why. It looks like a grid problem, but it's really a graph traversal problem in disguise.

LeetCode 200. Number of Islands →

You get a 2D grid where '1' is land and '0' is water. Count the islands — groups of land connected up, down, left, right. No diagonals.

Input:
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

The Core Idea

The whole algorithm is just this:

  1. Scan every cell.
  2. When you find land you haven't visited — that's a new island. Count it.
  3. Run BFS (or DFS) from that cell to visit the entire island, so it never gets counted again.

So the number of BFS calls = the number of islands. That's it.

DFS or BFS?

Both are O(m × n) in time, so correctness-wise either works. The difference is what happens under the hood.

  • Recursive DFS — shortest code, fastest to write. But recursion depth can hit O(m × n) in the worst case. Imagine the whole grid being one snake-shaped island — that's a deep call stack, and on large grids it can actually overflow.
  • BFS — uses an explicit queue on the heap, so it's safe. And for a grid, the queue peaks at only O(min(m, n)).

In an interview, recursive DFS is totally fine — as long as you mention the stack depth risk. That one sentence is the difference between "solved it" and "understands the tradeoffs." I went with BFS.

BFS Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
 
        rows, cols = len(grid), len(grid[0])
        visited = set()
        result = 0
 
        def bfs(r, c):
            queue = collections.deque([(r, c)])
            visited.add((r, c))
 
            directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
 
            while queue:
                row, col = queue.popleft()
                for dr, dc in directions:
                    newRow, newCol = row + dr, col + dc
                    if (0 <= newRow < rows and
                        0 <= newCol < cols and
                        grid[newRow][newCol] == '1' and
                        (newRow, newCol) not in visited):
 
                        visited.add((newRow, newCol))
                        queue.append((newRow, newCol))
 
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and (r, c) not in visited:
                    bfs(r, c)
                    result += 1
 
        return result

Time: O(m × n) / Space: O(m × n) — every cell is processed at most once, and the visited set holds up to every cell in the worst case.

The Detail That Actually Matters

Mark cells as visited when you add them to the queue, not when you take them out.

visited.add((newRow, newCol))
queue.append((newRow, newCol))

If you mark on dequeue instead, the same cell can enter the queue multiple times before it gets processed. The answer still comes out right, but you burn time and memory — and it's the kind of subtle mistake interviewers watch for.

Follow-ups Worth Knowing

  • Can we mutate the input? → Drop the visited set entirely and mark visited cells in place with grid[r][c] = '0'. Space for bookkeeping goes to O(1). Asking the interviewer whether mutation is allowed is itself a good signal.
  • What if the grid is huge? → This is where the DFS stack depth risk becomes real. BFS or iterative DFS with an explicit stack.
  • What about counting the biggest island instead? → That's LC 695. Max Area of Island — same skeleton, but BFS returns a size instead of just marking cells.

The skeleton here — scan, find unvisited land, flood it — is the same one behind Max Area of Island, Flood Fill, Surrounded Regions, and Rotting Oranges. Learn it once, reuse it everywhere.

← Back to Algorithm