LeetCode 200 Number of Islands: DFS, BFS and Union-Find Explained

Number of Islands is the most common "graph problem in disguise" in coding interviews. Nothing in the statement says "graph", but the moment you see a 2D grid where connected cells form groups, you are counting connected components. Once that clicks, the solution is a twelve-line flood fill.

The reason it stays popular is that it scales. An interviewer can ask the base problem in a phone screen, then push into stack depth, input mutation, Union-Find, dynamic land additions or shape comparison, depending on how fast you go. This guide covers all three standard solutions with code in Python, C++ and Java, a dry run, and the follow-ups. If grid traversal in general is new to you, read BFS and DFS graph interview problems alongside this.

The Problem and Why It's a Graph Problem

You get an m × n grid of characters, '1' for land and '0' for water. An island is a group of land cells connected horizontally or vertically, surrounded by water. Assume everything outside the grid is water. Return the number of islands.

1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Constraints on LeetCode: 1 ≤ m, n ≤ 300, cells are '0' or '1'. Note the cells are characters, not integers, which matters in Java and C++ where comparing against 1 instead of '1' is a silent bug.

The graph view

Model each land cell as a vertex. Put an edge between two land cells if they share a side. An island is then exactly a connected component of this graph, and the question is "how many connected components are there?"

The standard way to count components: loop over all vertices; whenever you find one that hasn't been visited, you've found a new component, so increment the counter and visit everything reachable from it. The graph here is implicit. We never build adjacency lists because a cell's neighbours are just (r±1, c) and (r, c±1).

Solution 1: DFS Flood Fill

The plan:

1. Scan. Visit every cell in row-major order.
2. Discover. If the cell is '1', it belongs to an island we haven't counted (otherwise the flood fill would already have erased it). Increment the count.
3. Sink. Run DFS from that cell, turning every reachable land cell into '0'. Overwriting with water doubles as the visited marker, so no extra array is needed.

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def sink(r: int, c: int) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
                return
            grid[r][c] = '0'                 # mark visited before recursing
            sink(r + 1, c)
            sink(r - 1, c)
            sink(r, c + 1)
            sink(r, c - 1)

        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    islands += 1
                    sink(r, c)
        return islands

class Solution {
    int rows, cols;
    void sink(vector<vector<char>>& g, int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] != '1') return;
        g[r][c] = '0';
        sink(g, r + 1, c);
        sink(g, r - 1, c);
        sink(g, r, c + 1);
        sink(g, r, c - 1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        rows = grid.size();
        cols = grid[0].size();
        int islands = 0;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (grid[r][c] == '1') {
                    ++islands;
                    sink(grid, r, c);
                }
        return islands;
    }
};

class Solution {
    private int rows, cols;

    public int numIslands(char[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        int islands = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == '1') {
                    islands++;
                    sink(grid, r, c);
                }
        return islands;
    }

    private void sink(char[][] g, int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] != '1') return;
        g[r][c] = '0';
        sink(g, r + 1, c);
        sink(g, r - 1, c);
        sink(g, r, c + 1);
        sink(g, r, c - 1);
    }
}

Why mark before recursing

The cell must be set to '0' before the four recursive calls. If you mark it after, the neighbour you recurse into will look back at this cell, still see '1', and recurse into it again, looping forever. "Mark on entry" is the rule for every flood fill.

The stack depth problem

On a 300 × 300 grid that is entirely land, a snake-like DFS can go 90,000 calls deep. C++ and Java usually survive this on LeetCode, but it's close to default stack limits elsewhere (Java's default thread stack is often around 512 KB to 1 MB depending on the platform). Python's default recursion limit is about 1,000, so the recursive Python version above can raise RecursionError on large inputs. Raising the limit with sys.setrecursionlimit is a band-aid that can still crash the interpreter. Mention this in an interview; it's exactly the kind of production awareness that separates a "hire" from a "lean hire". The fix is an explicit stack or BFS.

def num_islands_iterative(grid):
    rows, cols = len(grid), len(grid[0])
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            islands += 1
            grid[r][c] = '0'
            stack = [(r, c)]
            while stack:
                cr, cc = stack.pop()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'      # mark when pushing, not when popping
                        stack.append((nr, nc))
    return islands

Dry Run on Example 2

Grid (rows 0–3, columns 0–4):

Two things to notice. First, (2,2) and (3,3) touch only diagonally, so they are separate islands; 4-directional connectivity is the rule. Second, the DFS order inside the first island depends on the order of the four calls. With "down, up, right, left", from (0,0) the DFS goes down to (1,0), then right to (1,1), then up to (0,1). The order never changes the count.

Solution 2: BFS Flood Fill

BFS explores the island level by level from the starting cell using a queue. For counting it gives the same result as DFS, with no recursion. It also becomes the natural choice if a follow-up asks for distances, like "shortest bridge between two islands" (LeetCode 934) or the multi-source spread in Rotting Oranges.

from collections import deque
from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != '1':
                    continue
                islands += 1
                grid[r][c] = '0'
                q = deque([(r, c)])
                while q:
                    cr, cc = q.popleft()
                    for dr, dc in dirs:
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'   # mark on enqueue
                            q.append((nr, nc))
        return islands

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size(), islands = 0;
        const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] != '1') continue;
                ++islands;
                grid[r][c] = '0';
                queue<pair<int, int>> q;
                q.push({r, c});
                while (!q.empty()) {
                    int cr = q.front().first, cc = q.front().second;
                    q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int nr = cr + dr[k], nc = cc + dc[k];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                            grid[nr][nc] = '0';
                            q.push({nr, nc});
                        }
                    }
                }
            }
        }
        return islands;
    }
};

Mark on enqueue, not on dequeue

If you mark a cell visited only when you pop it, the same cell can be pushed several times by different neighbours before it's processed. The answer stays correct, but the queue can grow far larger than necessary and the run gets slower. Marking when you push guarantees each cell enters the queue at most once, which is what makes the O(m × n) bound hold cleanly.

BFS queue size is bounded by the "frontier" of the island, which is at most O(min(m, n)) for a single expanding diamond in many shapes, but O(m × n) is the safe worst-case statement in an interview.

Solution 3: Union-Find (Disjoint Set Union)

Union-Find counts components without any traversal. Start by treating every land cell as its own island. Then, for each land cell, union it with its land neighbour to the right and below (left and up are covered when those neighbours are processed). Every union that actually merges two different sets reduces the island count by one.

from typing import List

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dsu = DSU(rows * cols)
        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != '1':
                    continue
                count += 1
                idx = r * cols + c
                if r + 1 < rows and grid[r + 1][c] == '1' and dsu.union(idx, idx + cols):
                    count -= 1
                if c + 1 < cols and grid[r][c + 1] == '1' and dsu.union(idx, idx + 1):
                    count -= 1
        return count

class Solution {
    private int[] parent, rank;

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }

    public int numIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length, count = 0;
        parent = new int[rows * cols];
        rank = new int[rows * cols];
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != '1') continue;
                count++;
                int idx = r * cols + c;
                if (r + 1 < rows && grid[r + 1][c] == '1' && union(idx, idx + cols)) count--;
                if (c + 1 < cols && grid[r][c + 1] == '1' && union(idx, idx + 1)) count--;
            }
        }
        return count;
    }
}

Why only right and down?

Every adjacency is an unordered pair. The pair (cell, cell to its left) is the same as (left cell, its right neighbour), which was already considered when we processed the left cell. Checking two directions instead of four halves the union calls without missing any edge.

Union-Find also leaves the grid untouched, which some interviewers like. The cost is O(m × n) extra memory for parent and rank. For the full theory (why path compression plus union by rank gives near-constant time), see the Union-Find guide.

Complexity: DFS vs BFS vs Union-Find

Why O(m·n) for the traversals: the outer loop touches every cell once. Each cell is sunk at most once, and when sunk it checks four neighbours. So the total is about 5 × m × n constant-time operations. The α in Union-Find is the inverse Ackermann function, which is at most 4 for any input that fits in the universe; treat it as constant.

Follow-Ups: Max Area, Distinct Islands, Number of Islands II

Max Area of Island (LeetCode 695)

Instead of counting islands, return the size of the largest. Make the flood fill return the number of cells it sank.

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])
    best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            grid[r][c] = 0
            stack, area = [(r, c)], 0
            while stack:
                cr, cc = stack.pop()
                area += 1
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 0
                        stack.append((nr, nc))
            best = max(best, area)
    return best

Note that LeetCode 695 uses integers 0/1, not characters. Read each variant's input type.

Number of Distinct Islands (LeetCode 694)

Two islands are the same if one can be translated (not rotated or reflected) onto the other. Normalise each island by subtracting the coordinates of its first discovered cell, and store the sorted tuple of offsets in a set.

def num_distinct_islands(grid):
    rows, cols = len(grid), len(grid[0])
    shapes = set()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            grid[r][c] = 0
            stack, cells = [(r, c)], []
            while stack:
                cr, cc = stack.pop()
                cells.append((cr - r, cc - c))      # offset from the origin cell
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 0
                        stack.append((nr, nc))
            shapes.add(tuple(sorted(cells)))
    return len(shapes)

Because the scan is row-major, the origin cell is always the top-most, left-most cell of the island, so the same shape always produces the same offsets. Sorting makes the key independent of traversal order.

The harder version, LeetCode 711 (Distinct Islands II), also treats rotations and reflections as equal: generate all 8 transformations of each shape, normalise each, and use the lexicographically smallest as the canonical key.

Number of Islands II (LeetCode 305): land added over time

The grid starts as all water. You receive a list of positions that turn into land one by one, and after each you must report the island count. Re-running a flood fill after every addition is O(k × m × n) for k additions. Union-Find handles it online:

1. Add land. If the cell is already land, the count is unchanged. Otherwise mark it, make it its own set and increment the count.
2. Merge. For each of the four neighbours that is land, union. Every union that merges two different sets decrements the count.
3. Report. Append the current count.

def num_islands_2(m, n, positions):
    parent = {}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    count, result = 0, []
    for r, c in positions:
        if (r, c) in parent:                 # duplicate addition
            result.append(count)
            continue
        parent[(r, c)] = (r, c)
        count += 1
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if (nr, nc) in parent:
                ra, rb = find((r, c)), find((nr, nc))
                if ra != rb:
                    parent[rb] = ra
                    count -= 1
        result.append(count)
    return result

Total time is roughly O(k × α) for k additions (this sketch skips union by rank; path halving alone keeps it fast in practice). The duplicate-position check is a real test case on LeetCode and a common bug. This problem is the clearest answer to "when would you choose Union-Find over DFS?"

Other variants in one line each

For more grid-specific patterns (rotation, spiral order, DP on grids), see matrix and 2D grid interview problems.

How Number of Islands Shows Up in Interviews

This problem is a frequent pick at Amazon, Microsoft, Google, and Indian product companies such as Flipkart, Swiggy and PhonePe, often as the first question in a round. Interviewers are usually looking for these things:

• Naming the abstraction. Say "this is counting connected components in an implicit graph" in the first minute. It signals you'll handle the follow-ups.
• Asking about mutation. "Can I modify the grid, or should I keep it intact?" If you overwrite cells, say so. Some interviewers will ask you to restore it or use a visited array.
• Clean neighbour handling. A direction array like ((1,0),(-1,0),(0,1),(0,-1)) and a single bounds check read much better than four copy-pasted if blocks.
• Stack depth awareness. Volunteer the recursion risk and the BFS or explicit-stack fix.
• Correct complexity. O(m·n) time, O(m·n) worst-case space, with the reason.

Follow-up questions to prepare for

• "What if the grid is too large for memory, say 10⁶ × 10⁶, streamed row by row?" Process two rows at a time with Union-Find over the current and previous row, merging labels as you go. This is the classic connected-component labelling idea from image processing.
• "What if diagonals count?" Add four diagonal offsets to the direction array.
• "What if land keeps being added?" Union-Find (LeetCode 305), as above.
• "What if the grid wraps around (a torus)?" Use modular arithmetic for neighbours: (r + dr) % rows.
• "Can you parallelise it?" Split the grid into strips, count components per strip, then union across strip boundaries. Union-Find makes the merge step straightforward.

Common Mistakes

• Comparing with the wrong type. grid[r][c] == 1 on a char[][] in Java or C++ compiles but is always false. Use '1'.
• Marking visited too late. In DFS, mark before recursing. In BFS, mark when enqueuing.
• Bounds check after access. Check r and c are in range before reading grid[r][c], or you'll index out of bounds.
• Counting cells instead of islands. Increment the counter in the outer loop, once per flood fill start, not inside the DFS.
• Recursion depth in Python. Works on small tests, fails on the big all-land case. Use BFS.
• Forgetting the empty grid. LeetCode guarantees at least 1 × 1, but in a real interview ask; grid[0] on an empty list crashes.
• Union-Find without decrementing only on real merges. Decrement only when the two roots differ, or you'll undercount.

Once this feels comfortable, the natural next graph problems are Course Schedule (directed graphs and cycle detection) and Rotting Oranges (multi-source BFS). Together they cover most of what interviewers mean by "graph round" for SDE-1 and SDE-2 roles. And if recursion still feels shaky, the recursion for beginners guide covers the "trust the recursive call" mindset that flood fill depends on.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.