Problems

Ready to put your graph traversal skills to the test? These carefully selected LeetCode problems will help you master BFS and DFS techniques. Refer to our Code Templates for implementation patterns.

Easy Problems

1. Number of Islands

Brief: Count the number of islands in a 2D grid where ‘1’ represents land and ‘0’ represents water.
Why this pattern?: Each island is a connected component that can be explored using DFS or BFS.
Key Insight: Mark visited cells by changing ‘1’ to ‘0’ to avoid recounting the same island.

  flowchart TD;
    A[Start at Grid Cell] --> B{Cell is '1'?};
    B -->|Yes| C[Start DFS/BFS];
    B -->|No| D[Skip Cell];
    C --> E[Mark as Visited '0'];
    E --> F[Explore 4 Directions];
    F --> G{More Unvisited '1'?};
    G -->|Yes| F;
    G -->|No| H[Island Count++];
    H --> D;

function numIslands(grid) {
    if (!grid || !grid.length) return 0;

    let islands = 0;
    const rows = grid.length;
    const cols = grid[0].length;

    const dfs = (row, col) => {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === '0') {
            return;
        }

        grid[row][col] = '0';
        dfs(row + 1, col);
        dfs(row - 1, col);
        dfs(row, col + 1);
        dfs(row, col - 1);
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                islands++;
                dfs(i, j);
            }
        }
    }

    return islands;
}

def numIslands(grid):
    if not grid or not grid[0]:
        return 0

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

    def dfs(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return

        grid[row][col] = '0'
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                islands += 1
                dfs(i, j)

    return islands

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;
        int islands = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    dfs(grid, i, j, rows, cols);
                }
            }
        }

        return islands;
    }

    private void dfs(char[][] grid, int row, int col, int rows, int cols) {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0';
        dfs(grid, row + 1, col, rows, cols);
        dfs(grid, row - 1, col, rows, cols);
        dfs(grid, row, col + 1, rows, cols);
        dfs(grid, row, col - 1, rows, cols);
    }
}

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        int islands = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    dfs(grid, i, j, rows, cols);
                }
            }
        }

        return islands;
    }

private:
    void dfs(vector<vector<char>>& grid, int row, int col, int rows, int cols) {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0';
        dfs(grid, row + 1, col, rows, cols);
        dfs(grid, row - 1, col, rows, cols);
        dfs(grid, row, col + 1, rows, cols);
        dfs(grid, row, col - 1, rows, cols);
    }
};

func numIslands(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }

    rows, cols := len(grid), len(grid[0])
    islands := 0

    var dfs func(row, col int)
    dfs = func(row, col int) {
        if row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0' {
            return
        }

        grid[row][col] = '0'
        dfs(row+1, col)
        dfs(row-1, col)
        dfs(row, col+1)
        dfs(row, col-1)
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                islands++
                dfs(i, j)
            }
        }
    }

    return islands
}

def num_islands(grid)
    return 0 if grid.nil? || grid.empty?

    rows, cols = grid.length, grid[0].length
    islands = 0

    dfs = lambda do |row, col|
        return if row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0'

        grid[row][col] = '0'
        dfs.call(row + 1, col)
        dfs.call(row - 1, col)
        dfs.call(row, col + 1)
        dfs.call(row, col - 1)
    end

    (0...rows).each do |i|
        (0...cols).each do |j|
            if grid[i][j] == '1'
                islands += 1
                dfs.call(i, j)
            end
        end
    end

    islands
end

Time Complexity:

O(m × n)

| Space Complexity:

O(m × n)

(recursion stack)

Medium Problems

2. Clone Graph

Brief: Create a deep copy of a connected undirected graph where each node has a value and list of neighbors.
Why this pattern?: We need to visit every node exactly once and maintain the original graph’s structure.
Key Insight: Use a hash map to track original-to-clone node pairs and prevent infinite loops.

  graph TD;
    A[Original Node] --> B[Create Clone];
    B --> C{Clone Exists?};
    C -->|No| D[Store in Map];
    C -->|Yes| E[Return Existing Clone];
    D --> F[Clone Neighbors];
    F --> G[Connect to Clone];
    G --> H[Recurse on Neighbors];
    H --> I[Complete Clone Structure];

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

    const visited = new Map();

    function dfs(curr) {
        if (visited.has(curr.val)) {
            return visited.get(curr.val);
        }

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

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

        return clone;
    }

    return dfs(node);
}

def cloneGraph(node):
    if not node:
        return None

    visited = {}

    def dfs(curr):
        if curr.val in visited:
            return visited[curr.val]

        clone = Node(curr.val)
        visited[curr.val] = clone

        for neighbor in curr.neighbors:
            clone.neighbors.append(dfs(neighbor))

        return clone

    return dfs(node)

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Integer, Node> visited = new HashMap<>();
        return dfs(node, visited);
    }

    private Node dfs(Node node, Map<Integer, Node> visited) {
        if (visited.containsKey(node.val)) {
            return visited.get(node.val);
        }

        Node clone = new Node(node.val, new ArrayList<>());
        visited.put(node.val, clone);

        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(dfs(neighbor, visited));
        }

        return clone;
    }
}

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;

        unordered_map<int, Node*> visited;
        return dfs(node, visited);
    }

private:
    Node* dfs(Node* node, unordered_map<int, Node*>& visited) {
        if (visited.find(node->val) != visited.end()) {
            return visited[node->val];
        }

        Node* clone = new Node(node->val);
        visited[node->val] = clone;

        for (Node* neighbor : node->neighbors) {
            clone->neighbors.push_back(dfs(neighbor, visited));
        }

        return clone;
    }
};

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    visited := make(map[int]*Node)

    var dfs func(*Node) *Node
    dfs = func(curr *Node) *Node {
        if clone, exists := visited[curr.Val]; exists {
            return clone
        }

        clone := &Node{Val: curr.Val}
        visited[curr.Val] = clone

        for _, neighbor := range curr.Neighbors {
            clone.Neighbors = append(clone.Neighbors, dfs(neighbor))
        }

        return clone
    }

    return dfs(node)
}

def clone_graph(node)
    return nil if node.nil?

    visited = {}

    dfs = lambda do |curr|
        return visited[curr.val] if visited.key?(curr.val)

        clone = Node.new(curr.val)
        visited[curr.val] = clone

        curr.neighbors.each do |neighbor|
            clone.neighbors.push(dfs.call(neighbor))
        end

        clone
    end

    dfs.call(node)
end

Time Complexity:

O(N + M)

| Space Complexity:

O(N)

Hard Problems

3. Word Ladder

Brief: Find the shortest transformation sequence from beginWord to endWord where each step changes exactly one letter.
Why this pattern?: This is a shortest path problem in an implicit graph where words are nodes and valid transformations are edges.
Key Insight: Use BFS to guarantee the shortest path and generate neighbors by changing each character to all possible letters.

  flowchart TD;
    A[Begin Word] --> B[Generate All Possible Words];
    B --> C{Word in Dictionary?};
    C -->|No| D[Skip];
    C -->|Yes| E{Not Visited?};
    E -->|No| D;
    E -->|Yes| F[Mark Visited & Enqueue];
    F --> G{Word == EndWord?};
    G -->|Yes| H[Return Steps];
    G -->|No| I[Continue BFS];
    D --> I;
    I --> J{Queue Empty?};
    J -->|No| B;
    J -->|Yes| K[Return 0];

function ladderLength(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 [currentWord, steps] = queue.shift();

        for (let i = 0; i < currentWord.length; i++) {
            for (let charCode = 97; charCode <= 122; charCode++) {
                const newChar = String.fromCharCode(charCode);
                const newWord = currentWord.substring(0, i) + newChar + currentWord.substring(i + 1);

                if (newWord === endWord) {
                    return steps + 1;
                }

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

    return 0;
}

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    queue = deque([(beginWord, 1)])
    visited = set([beginWord])

    while queue:
        current_word, steps = queue.popleft()

        for i in range(len(current_word)):
            for char_code in range(ord('a'), ord('z') + 1):
                new_char = chr(char_code)
                new_word = current_word[:i] + new_char + current_word[i+1:]

                if new_word == endWord:
                    return steps + 1

                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))

    return 0

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int steps = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentWord = queue.poll();

                for (int j = 0; j < currentWord.length(); j++) {
                    char[] chars = currentWord.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String newWord = new String(chars);

                        if (newWord.equals(endWord)) {
                            return steps + 1;
                        }

                        if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                            visited.add(newWord);
                            queue.offer(newWord);
                        }
                    }
                }
            }
            steps++;
        }

        return 0;
    }
}

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;

        queue<pair<string, int>> q;
        unordered_set<string> visited;
        q.push({beginWord, 1});
        visited.insert(beginWord);

        while (!q.empty()) {
            auto [currentWord, steps] = q.front();
            q.pop();

            for (int i = 0; i < currentWord.length(); i++) {
                string temp = currentWord;
                for (char c = 'a'; c <= 'z'; c++) {
                    temp[i] = c;
                    string newWord = temp;

                    if (newWord == endWord) {
                        return steps + 1;
                    }

                    if (wordSet.find(newWord) != wordSet.end() && visited.find(newWord) == visited.end()) {
                        visited.insert(newWord);
                        q.push({newWord, steps + 1});
                    }
                }
            }
        }

        return 0;
    }
};

func ladderLength(beginWord string, endWord string, wordList []string) int {
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }
    if !wordSet[endWord] {
        return 0
    }

    queue := []pair{{beginWord, 1}}
    visited := make(map[string]bool)
    visited[beginWord] = true

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        currentWord, steps := current.word, current.steps

        for i := 0; i < len(currentWord); i++ {
            for c := 'a'; c <= 'z'; c++ {
                newWord := currentWord[:i] + string(c) + currentWord[i+1:]

                if newWord == endWord {
                    return steps + 1
                }

                if wordSet[newWord] && !visited[newWord] {
                    visited[newWord] = true
                    queue = append(queue, pair{newWord, steps + 1})
                }
            }
        }
    }

    return 0
}

type pair struct {
    word  string
    steps int
}

def ladder_length(begin_word, end_word, word_list)
    word_set = Set.new(word_list)
    return 0 unless word_set.include?(end_word)

    queue = [[begin_word, 1]]
    visited = Set.new([begin_word])

    until queue.empty?
      current_word, steps = queue.shift

      (0...current_word.length).each do |i|
        ('a'..'z').each do |char|
          new_word = current_word[0...i] + char + current_word[i+1..-1]

          return steps + 1 if new_word == end_word

          if word_set.include?(new_word) && !visited.include?(new_word)
            visited.add(new_word)
            queue.push([new_word, steps + 1])
          end
        end
      end
    end

    0
end

Time Complexity:

O(M² × N)

| Space Complexity:

O(M × N)

Recommended Study Order

Start with Number of Islands to master grid-based DFS/BFS, then move to Clone Graph to understand graph node manipulation, and finally tackle Word Ladder to work with implicit graphs and shortest path algorithms.

Pro Tip: For BFS problems like Word Ladder, always mark nodes as visited when you add them to the queue, not when you process them. This prevents adding the same node multiple times.