Skip to content
Coding Patterns - Guide to 30 Core Algorithm Patterns
Graph Traversal: Complete Guide with BFS and DFS Examples
Graph Traversal: Practice Problems with Full Solutions

Graph Traversal: Practice Problems with Full Solutions

Welcome to the practice problems for graph traversal. If you need a refresher on the code, the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

  1. Flood Fill teaches DFS on a grid with nothing else going on. It is the cleanest possible first contact with the visited check.
  2. Clone Graph moves from grids to node objects. The map does double duty as the visited set and the connection table.
  3. Rotting Oranges is BFS with a timer. It shows the level-by-level queue pattern and how multiple sources share one queue.
  4. Pacific Atlantic Water Flow reverses the direction of the search. You start from the edges and flow uphill instead of searching from each cell.
  5. Word Ladder hides the graph. The nodes are words and the edges are single-letter changes, so the graph is built implicitly as you search.
  6. Bus Routes is the hardest. The BFS moves between stops, but the unit you pay for is the bus route, and a stop can belong to many routes.
The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Flood Fill

LeetCode 733 | Difficulty: Easy

Brief: Paint the starting cell and every cell connected to it that shares its original color with a new color.

Why this pattern: The connected region is a graph component in a grid. A DFS from the start cell visits exactly that component, and nothing else.

Key Insight: Save the original color before painting. The search only spreads through cells that still hold the original color, so repainted cells automatically become barriers that stop the recursion.

Visual:

    graph TD
    S["Start at (sr, sc), save original color"] --> B{"In bounds and still original color?"}
    B -->|Yes| P["Paint it, recurse on 4 neighbors"]
    P --> B
    B -->|No| R["Return to caller"]

Code:

var floodFill = function(image, sr, sc, color) {
    const original = image[sr][sc];
    if (original === color) return image;

    const rows = image.length;
    const cols = image[0].length;

    function fill(r, c) {
        // Painting before recursing is the visited check. A
        // painted cell no longer matches the original color.
        if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] !== original) return;
        image[r][c] = color;
        fill(r + 1, c);
        fill(r - 1, c);
        fill(r, c + 1);
        fill(r, c - 1);
    }

    fill(sr, sc);
    return image;
};

The early return when the start cell already has the target color prevents infinite recursion, since painted cells would otherwise keep matching the original color. Complexity is

O(R × C)
time and space, where R is the row count and C is the column count. Every cell is visited at most once, and the recursion stack can reach every cell in the worst case.

Medium Problems

2. Clone Graph

LeetCode 133 | Difficulty: Medium

Brief: Given a connected undirected graph where each node has a value and a list of neighbors, return a deep copy of the graph.

Why this pattern: A deep copy must visit every node and every edge once. DFS does exactly that, and the map between original and clone nodes replaces the usual visited set.

Key Insight: Store the clone in the map before recursing on neighbors. When the graph has cycles, the recursion would otherwise loop forever on the first back edge.

Visual:

    graph TD
    A["Visit original node"] --> B{"Clone already in map?"}
    B -->|Yes| C["Return existing clone"]
    B -->|No| D["Create clone, store in map"]
    D --> E["Recurse on each neighbor"]
    E --> F["Link clone to neighbor clones"]
    F --> C

Code:

function Node(val, neighbors) {
    this.val = val === undefined ? 0 : val;
    this.neighbors = neighbors === undefined ? [] : neighbors;
}

var cloneGraph = function(node) {
    if (!node) return null;

    const clones = new Map();

    function dfs(curr) {
        // The clone is stored before recursing, so a back
        // edge finds it and the recursion terminates.
        if (clones.has(curr)) return clones.get(curr);

        const clone = new Node(curr.val);
        clones.set(curr, clone);

        for (const neighbor of curr.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        return clone;
    }

    return dfs(node);
};

The order of operations is the whole problem. The clone goes into the map before its neighbors are processed, because a cycle can lead back to the current node from any depth. Complexity is

O(N)
time and space for N nodes. Each node is cloned once, and the map plus the recursion stack hold one entry per node.

3. Rotting Oranges

LeetCode 994 | Difficulty: Medium

Brief: Every minute, each rotten orange rots its adjacent fresh oranges. Return the minutes until no fresh orange remains, or -1 if some can never rot.

Why this pattern: All rotten oranges spread at the same speed, so this is a multi-source BFS where one minute is one layer of the queue.

Key Insight: Seed the queue with every rotten orange before the first iteration. Draining the queue one layer at a time converts layer count into minutes.

Visual:

    graph TD
    A["Queue all rotten oranges, count fresh"] --> C{"Queue not empty and fresh remain?"}
    C -->|Yes| D["Drain one full layer, one minute"]
    D --> E["Rot adjacent fresh oranges, enqueue"]
    E --> C
    C -->|No| F["Return minutes, or -1 if fresh remain"]

Code:

var orangesRotting = function(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    const queue = [];
    let fresh = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 2) {
                queue.push([r, c]);
            } else if (grid[r][c] === 1) {
                fresh++;
            }
        }
    }

    let minutes = 0;
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

    while (queue.length > 0 && fresh > 0) {
        minutes++;
        // The size is captured once, so one loop drains
        // exactly one minute's layer.
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const [r, c] = queue.shift();
            for (const [dr, dc] of directions) {
                const nr = r + dr;
                const nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.push([nr, nc]);
                }
            }
        }
    }

    return fresh === 0 ? minutes : -1;
};

The layer-draining loop is the pattern-specific trick. Without the size snapshot, one minute would rot only one orange instead of the whole layer. Complexity is

O(R × C)
time and space, since every cell enters the queue at most once.

4. Pacific Atlantic Water Flow

LeetCode 417 | Difficulty: Medium

Brief: Given a height grid where water flows from a cell to neighbors of equal or lower height, find every cell that can reach both the Pacific (top and left edges) and the Atlantic (bottom and right edges).

Why this pattern: Searching from each cell is wasteful. Reversing the flow and searching from the edges visits every cell at most twice, once per ocean.

Key Insight: Start DFS at the border cells and move to neighbors of equal or higher height. A cell is in the answer only if both searches reach it.

Visual:

    graph TD
    A["DFS from top row and left column"] --> B["Mark cells that reach the Pacific"]
    B --> C["DFS from bottom row and right column"]
    C --> D["Mark cells that reach the Atlantic"]
    D --> E["Return cells marked by both searches"]

Code:

var pacificAtlantic = function(heights) {
    const rows = heights.length;
    const cols = heights[0].length;
    const pacific = new Set();
    const atlantic = new Set();

    function dfs(r, c, seen, prevHeight) {
        // Water drains downhill, so the reverse search only
        // climbs to cells of equal or higher height.
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        const key = r + ',' + c;
        if (seen.has(key) || heights[r][c] < prevHeight) return;

        seen.add(key);
        dfs(r + 1, c, seen, heights[r][c]);
        dfs(r - 1, c, seen, heights[r][c]);
        dfs(r, c + 1, seen, heights[r][c]);
        dfs(r, c - 1, seen, heights[r][c]);
    }

    for (let c = 0; c < cols; c++) {
        dfs(0, c, pacific, heights[0][c]);
        dfs(rows - 1, c, atlantic, heights[rows - 1][c]);
    }
    for (let r = 0; r < rows; r++) {
        dfs(r, 0, pacific, heights[r][0]);
        dfs(r, cols - 1, atlantic, heights[r][cols - 1]);
    }

    const result = [];
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            const key = r + ',' + c;
            if (pacific.has(key) && atlantic.has(key)) {
                result.push([r, c]);
            }
        }
    }
    return result;
};

The reversed flow condition is the pattern-specific trick. Instead of simulating water draining from every cell, the search starts at the oceans and only climbs, so each cell is visited at most once per ocean. Complexity is

O(R × C)
time and space, and the answer is the intersection of the two reachability sets.

Hard Problems

5. Word Ladder

LeetCode 127 | Difficulty: Hard

Brief: Given a start word, an end word, and a dictionary, return the length of the shortest transformation sequence where each step changes one letter and every intermediate word is in the dictionary.

Why this pattern: The words form an implicit graph. Each word is a node and each valid one-letter change is an edge. The shortest sequence is a shortest path, so BFS is the correct traversal.

Key Insight: Do not prebuild the graph. Generate the 26 neighbors of each word on the fly and test them against the dictionary set. That keeps the graph implicit and the search lazy.

Visual:

    graph LR
    A["hit"] --> B["hot"]
    B --> C["dot"]
    C --> D["dog"]
    D --> E["cog"]

Code:

var ladderLength = function(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;

    const queue = [[beginWord, 1]];
    const visited = new Set([beginWord]);

    while (queue.length > 0) {
        const [word, steps] = queue.shift();

        for (let i = 0; i < word.length; i++) {
            // The graph is implicit. Only mutations that land
            // in the dictionary become edges.
            for (let code = 97; code <= 122; code++) {
                const next = word.substring(0, i) + String.fromCharCode(code) + word.substring(i + 1);
                if (next === endWord) return steps + 1;

                if (wordSet.has(next) && !visited.has(next)) {
                    visited.add(next);
                    queue.push([next, steps + 1]);
                }
            }
        }
    }
    return 0;
};

Two choices make this problem fast. The dictionary becomes a set, so membership checks are constant time. Neighbors are generated on demand instead of prebuilding an adjacency list, which would waste memory on mutations that are not in the dictionary. Complexity is

O(M² × N)
time and
O(M × N)
space, where M is the word length and N is the dictionary size. Each of the N words can spawn 26M candidate mutations, and each mutation costs O(M) to build.

6. Bus Routes

LeetCode 815 | Difficulty: Hard

Brief: Given a list of bus routes where each route is a list of stops, return the minimum number of buses needed to travel from a source stop to a target stop, or -1 if it is impossible.

Why this pattern: The stops form an implicit graph, but the cost is per route, not per stop. BFS still finds the minimum, as long as each level of the queue represents one bus ride.

Key Insight: Build a map from each stop to the routes that serve it, and mark routes as taken instead of trying to track individual transfers. A stop can belong to many routes, and taking any of them costs one bus.

Visual:

    graph TD
    A["Source stop"] --> B["Routes that serve it"]
    B --> C["All stops on those routes"]
    C --> D{"Target stop found?"}
    D -->|Yes| E["Return buses taken"]
    D -->|No| F["Next layer: routes for the new stops"]
    F --> C

Code:

var numBusesToDestination = function(routes, source, target) {
    if (source === target) return 0;

    const stopToRoutes = new Map();
    for (let i = 0; i < routes.length; i++) {
        for (const stop of routes[i]) {
            if (!stopToRoutes.has(stop)) stopToRoutes.set(stop, []);
            stopToRoutes.get(stop).push(i);
        }
    }

    const queue = [source];
    const visitedStops = new Set([source]);
    const visitedRoutes = new Set();
    let buses = 0;

    while (queue.length > 0) {
        buses++;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const stop = queue.shift();
            // Each route is boarded once, since the first
            // time it is reached is the cheapest time.
            for (const routeIdx of stopToRoutes.get(stop) || []) {
                if (visitedRoutes.has(routeIdx)) continue;
                visitedRoutes.add(routeIdx);
                for (const nextStop of routes[routeIdx]) {
                    if (nextStop === target) return buses;
                    if (!visitedStops.has(nextStop)) {
                        visitedStops.add(nextStop);
                        queue.push(nextStop);
                    }
                }
            }
        }
    }
    return -1;
};

The route-level visited set is the trick that separates this from a plain stop BFS. Stops can be reached from many routes, but a route only ever needs to be boarded once, because the first time you reach it is also the cheapest. Marking routes as taken keeps the queue from exploding. Complexity is

O(S)
time, where S is the total number of stops across all routes, and
O(S + B)
space, where B is the number of routes. Each route is scanned once and each stop is enqueued at most once.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

Next Steps

These six problems cover the full arc of the pattern. You get grid DFS, node-level traversal, multi-source BFS with layer counting, reverse-flow search, and implicit graphs at two levels of difficulty. If Flood Fill still takes effort, go back to the code templates and drill the skeleton until the queue and the visited set feel automatic. The harder problems are all the same skeleton with one new idea bolted on.

Done with these problems? The app has more, plus a review system that brings problems back right before you would forget them. Continue your prep .