Blind 75 Visualized

#45 · Graphs

Number of Islands

Given an m × n grid of "1" (land) and "0" (water), count the islands. An island is land connected horizontally or vertically; diagonal contact does not count.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Grid as an implicit graph

Each cell is a vertex and its four neighbours are its edges, so no adjacency list is stored. Counting islands is counting connected components of the land vertices.

Memory layout

The grid itself, row by row. A neighbour is found by adding (±1, 0) or (0, ±1) to the row and column, with a bounds check.

OperationCost
timeO(m·n): each cell is entered a constant number of times
spaceO(m·n) worst case for the DFS stack, BFS queue, or union-find array

Union-Find (disjoint set union)

Keeps a partition of cells into sets. find returns a set's leader; union joins two sets. Starting with every land cell alone and merging neighbouring land cells leaves one set per island.

Memory layout

A flat integer array parent[] of size m·n; path compression keeps the trees shallow.

OperationCost
find / unionO(α(n)), practically constant

Why it fits

  • An island is a connected component, and any graph search (DFS, BFS) from one land cell reaches exactly the cells of its island and no others.
  • Counting the searches you have to start is counting islands: a cell not yet reached by a previous search must belong to a new island.
  • Union-Find reaches the same answer without any traversal and also works when land appears over time, because merging is incremental.

Why alternatives degrade

Counting land cells:
The number of land cells says nothing about how they are connected: 4 land cells can be 1 island or 4 islands.
Scanning for "corner" patterns:
Local patterns cannot tell whether two far-apart parts of a shape are connected (for example around a U-shaped island).
Diagonal connectivity:
The problem says horizontal and vertical only; diagonal neighbours would merge (2,2) and (3,3) here and give the wrong answer.

Four approaches, from naive to production

1 · beginner

DFS with a visited set

time O(m·n)space O(m·n)

Scan every cell. When an unvisited land cell is found, start a depth-first flood from it that marks every connected land cell in a set of "row,column" texts, then count one island.

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    set<string> visited;
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols) return;
        string key = to_string(r) + "," + to_string(c);
        if (grid[r][c] == '0' || visited.count(key)) return;
        visited.insert(key);
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    };
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1' && !visited.count(to_string(r) + "," + to_string(c))) {
                dfs(r, c);
                count++;
            }
        }
    }
    return count;
}

Flaws & bottlenecks

  • Each visited cell costs building a text key and hashing it, much slower than an index into an array.
  • The visited set can hold every land cell.
  • Recursion depth can reach m·n for a snake-shaped island, which may overflow the call stack on a big grid.

Interviewer cross-questions

Why does counting DFS starts count islands?

Say: A flood visits exactly one island, marking all of it. Any land cell still unmarked afterwards must be in a different island, so each new start is a new island.

What is the time complexity?

Say: Each cell is scanned once by the double loop and entered by DFS at most four times (once per neighbour plus the start), so O(m·n).

How would you avoid the string keys?

Say: Use a boolean matrix, or a single integer r·cols + c as the key. Better still, mark the grid in place.

2 · intermediate

BFS with a visited matrix

time O(m·n)space O(m·n)

Scan the grid; at an unvisited land cell, count an island and flood it with a queue. A cell is marked reached when it is queued, so it is never queued twice.

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int count = 0;
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '0' || visited[r][c]) continue;
            count++;
            visited[r][c] = true;
            queue<pair<int, int>> q; q.push({r, c});
            while (!q.empty()) {
                auto [cr, cc] = q.front(); q.pop();
                for (auto& d : dirs) {
                    int nr = cr + d[0], nc = cc + d[1];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    if (grid[nr][nc] == '0' || visited[nr][nc]) continue;
                    visited[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
    }
    return count;
}

Flaws & bottlenecks

  • Needs an extra m × n matrix of flags.
  • Removing from the front of an array queue can be O(n) in some languages; use a real queue.
  • A BFS queue can hold up to the island's perimeter, which for a big blob is O(min(m, n)) but O(m·n) in the worst case.

Interviewer cross-questions

Why mark a cell when queuing and not when taking it out?

Say: If you wait until dequeue, the same cell can be queued by several neighbours before it is processed, growing the queue and repeating work.

BFS or DFS: which is better here?

Say: Both are O(m·n). BFS uses a queue so there is no recursion-depth risk; DFS recursion is shorter to write but can overflow the stack on large islands.

Can you drop the visited matrix?

Say: Yes: overwrite visited land with water in the grid itself, as the next approach does.

3 · advanced

Sink land in place (DFS)

time O(m·n)space O(m·n) worst-case recursion

When land is found, count an island and run a flood that overwrites every connected land cell with water. The grid is the visited record, so no extra memory is needed beyond the recursion.

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    function<void(int, int)> sink = [&](int r, int c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
        grid[r][c] = '0';
        sink(r + 1, c);
        sink(r - 1, c);
        sink(r, c + 1);
        sink(r, c - 1);
    };
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                count++;
                sink(r, c);
            }
        }
    }
    return count;
}

Flaws & bottlenecks

  • It destroys the input grid; copy it first if the caller needs it again.
  • Deep recursion on a large snake-like island can overflow the stack.
  • Not usable when the grid is read-only or shared between threads.

Interviewer cross-questions

Is mutating the input acceptable?

Say: Often yes in interviews if you say so. In production, copy the grid (O(m·n) memory) or use a separate visited structure so callers are not surprised.

How do you avoid the recursion limit?

Say: Use an explicit stack or queue (iterative DFS or BFS). The logic is the same; only the container changes.

Why check the water condition inside the same test as the bounds?

Say: Both conditions mean "stop here". Putting bounds first protects the grid access, and checking water after it also stops on cells that were already sunk.

4 · expert

Union-Find over land cells

time O(m·n · α(m·n))space O(m·n)

Start with every land cell as its own set and count them. For each land cell, merge it with its right and lower land neighbours; each merge that joins two different sets lowers the count by one. The final count is the number of islands.

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    vector<int> parent(rows * cols);
    int count = 0;
    for (int i = 0; i < (int)parent.size(); i++) {
        parent[i] = i;
        if (grid[i / cols][i % cols] == '1') count++;
    }
    function<int(int)> find = [&](int x) -> int {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '0') continue;
            int nbs[2][2] = {{r + 1, c}, {r, c + 1}};
            for (auto& nb : nbs) {
                int nr = nb[0], nc = nb[1];
                if (nr >= rows || nc >= cols || grid[nr][nc] == '0') continue;
                int a = find(r * cols + c), b = find(nr * cols + nc);
                if (a != b) {
                    parent[a] = b;
                    count--;
                }
            }
        }
    }
    return count;
}

Flaws & bottlenecks

  • Needs a parent array the size of the whole grid, even for mostly water.
  • Without union by size or rank the trees can grow tall (path halving alone keeps it fast in practice).
  • For a one-time count, a plain DFS is simpler; union-find pays off when land is added over time.

Interviewer cross-questions

When is union-find better than DFS here?

Say: When cells turn into land one at a time and you need the island count after each change (Number of Islands II). Each addition is a few unions and the count is updated incrementally; a DFS would have to recount from scratch.

Why look only right and down?

Say: Every adjacent pair of cells appears once as (cell, its right) or (cell, its lower). Checking left and up as well would repeat the same pairs.

What does path halving do?

Say: While following parent links, it points each visited node at its grandparent, flattening the tree a little on every find so later finds are almost constant time.

Synchronized code walkthrough

Showing: DFS with a visited set — shares the player above; click any step to jump.

int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    set<string> visited;
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols) return;
        string key = to_string(r) + "," + to_string(c);
        if (grid[r][c] == '0' || visited.count(key)) return;
        visited.insert(key);
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    };
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1' && !visited.count(to_string(r) + "," + to_string(c))) {
                dfs(r, c);
                count++;
            }
        }
    }
    return count;
}