Breadth-First Search (BFS)

Problem: A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Every minute, each rotten orange rots its 4-directional fresh neighbours. Return the minutes until no fresh orange is left, or -1 if some can never rot.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 10 · grid[i][j] is 0, 1, or 2.

From brute force to the pattern: Simulating minute by minute by rescanning the whole grid is O((r · c)²). A multi-source BFS spreads from all rotten oranges together and touches each cell once: O(r · c).

Spot it: "every minute, spreads to adjacent" with many starting rotten oranges = multi-source, level-by-level BFS.

Key insight: Put all rotten oranges in the queue at minute 0. Each frozen-size round is one minute. Count the fresh oranges up front so you can tell at the end whether any were unreachable.

Approach:

1. Scan the grid once. Push every rotten orange into the queue and count the fresh ones.
2. While the queue is non-empty and fresh oranges remain, process one level (frozen size). That's one minute.
3. For each popped cell, rot every fresh 4-neighbour: set it to 2 (mark on enqueue), decrease fresh, and enqueue it.
4. After each level, add 1 to minutes.
5. Return minutes if fresh == 0, else -1.

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        # The queue holds (row, col) of rotten oranges that will spread next.
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        fresh = 0
        # Step 1: scan the grid once. Every rotten orange is a starting point,
        # and we count the fresh ones so we know when we are finished.
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh = fresh + 1
        # The 4 moves as (row change, col change): down, up, right, left.
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        minutes = 0
        # Step 2: go on while something can still spread AND something is still fresh.
        while len(queue) > 0 and fresh > 0:
            # Freeze the size: these are exactly the oranges that spread THIS minute.
            level_size = len(queue)
            for _ in range(level_size):
                cell = queue.popleft()
                row = cell[0]
                col = cell[1]
                for direction in directions:
                    new_row = row + direction[0]
                    new_col = col + direction[1]
                    # Skip cells outside the grid.
                    if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= cols:
                        continue
                    if grid[new_row][new_col] == 1:
                        grid[new_row][new_col] = 2    # rot it now = mark when enqueued
                        fresh = fresh - 1
                        queue.append((new_row, new_col))
            # One whole level is done, so one minute has passed.
            minutes = minutes + 1
        # Step 3: a fresh orange that is left over could never be reached.
        if fresh == 0:
            return minutes
        else:
            return -1

What the code is doing, line by line:

1. rows and cols store the grid size so the bounds checks are easy to read.
2. Step 1 (scan): the double for loop visits every cell. Rotten cells (2) go into the queue as (row, col) pairs; fresh cells (1) are only counted in fresh.
3. directions lists the 4 moves as (row change, col change). Adding one to a cell's position gives a neighbour.
4. Step 2 (spread): the while loop runs while there are rotten oranges to spread from and fresh oranges left to rot. The second condition stops us counting an extra empty minute at the end.
5. level_size = len(queue) freezes this minute's rotten oranges. Each one is popped and split into row and col by indexing (cell[0], cell[1]).
6. For each direction, out-of-grid neighbours are skipped with continue. A fresh neighbour is set to 2 straight away (so nobody rots it twice), fresh goes down by 1, and it is queued for the next minute.
7. After the whole level, minutes goes up by 1.
8. Step 3: if fresh reached 0, return the minutes; otherwise some orange was walled off, so return -1.

Dry run on grid = [[2,1,1],[1,1,0],[0,1,1]] (answer 4):

fresh is now 0, so the loop stops with minutes = 4 and the code returns 4.

Edge cases to test:

• No fresh oranges at the start → 0.
• A fresh orange that can never be reached → −1.
• No rotten oranges but some fresh ones → −1.

Complexity: O(R·C) time and space.

Problem: A 4-wheel lock starts at "0000". One move turns one wheel up or down by one (9 wraps to 0). Avoid every code in deadends. Return the minimum number of moves to reach target, or -1.

Solve it on LeetCode ↗

Constraints: 1 ≤ deadends.length ≤ 500 · deadends[i].length == 4 · target.length == 4 · target will not be in the list deadends. · target and deadends[i] consist of digits only.

From brute force to the pattern: DFS over all combinations doesn't find the minimum number of moves. BFS over the 10,000 states, each with 8 neighbours, finds it in O(10⁴ · 8).

Spot it: "minimum number of turns", and each turn costs 1. The graph is implicit: nodes are the 10⁴ codes, and every code has 8 neighbours.

Key insight: Generate neighbours on the fly and treat deadends as pre-visited walls. Check whether "0000" itself is a deadend.

Approach:

1. Put the deadends in a set. If "0000" is a deadend, return -1.
2. BFS from ("0000", 0) with a seen set.
3. Pop a code. If it's the target, return the number of turns.
4. Generate its 8 neighbours (each of 4 wheels, ±1 with wrap-around), and enqueue the ones not seen and not dead.
5. If the queue empties, return -1.

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        # A set makes "is this code a deadend?" an instant check.
        dead = set(deadends)
        if "0000" in dead:
            return -1               # stuck before the first move
        seen = set()
        seen.add("0000")
        # The queue holds (code, turns used to reach it).
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        queue.append(("0000", 0))
        while len(queue) > 0:
            pair = queue.popleft()
            code = pair[0]
            turns = pair[1]
            if code == target:
                return turns        # first time we pop the target = fewest turns
            # Build the 8 neighbours: each of the 4 wheels turned up (+1) or down (-1).
            for i in range(4):
                digit = int(code[i])
                for step in [1, -1]:
                    # % 10 wraps around: 9 + 1 becomes 0, and 0 - 1 becomes 9.
                    new_digit = (digit + step) % 10
                    next_code = code[:i] + str(new_digit) + code[i + 1:]
                    if next_code not in seen and next_code not in dead:
                        seen.add(next_code)        # mark when enqueued
                        queue.append((next_code, turns + 1))
        # Every reachable code was tried and none was the target.
        return -1

What the code is doing, line by line:

1. dead = set(deadends) turns the list into a set, so "is this a deadend?" takes constant time.
2. If "0000" itself is dead we can't move at all, so return -1.
3. The queue holds pairs (code, turns). Each pop is split by indexing: pair[0] is the code, pair[1] the number of turns used.
4. If the popped code is the target, BFS guarantees turns is the minimum, so return it.
5. Otherwise build the 8 neighbours. For each wheel i (0 to 3) and each step (+1 or -1), (digit + step) % 10 gives the new digit with wrap-around, and code[:i] + str(new_digit) + code[i + 1:] glues the string back together with that one digit changed.
6. A neighbour that is neither seen nor dead is marked seen and queued with turns + 1.
7. If the queue empties, the target can't be reached: return -1.

Dry run on deadends = ["0201","0101","0102","1212","2002"], target = "0202" (answer 6). The queue gets large, so this table counts codes per BFS level:

Every 4-turn route (like "0000" → "0100" → "0200" → "0201" → "0202") passes through a deadend ("0101", "0201" or "0102"), which is why the answer is 6 turns instead of 4.

Edge cases to test:

• "0000" itself is a dead end → −1.
• The target is "0000" → 0.
• Wrap-around between 9 and 0.

Complexity: O(104 · 8 · 4) time, i.e. constant for this fixed lock; O(104) space.

Problem: Given a tree of n nodes (as undirected edges), return every node that, when chosen as the root, gives the minimum possible height.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 2 * 10⁴ · edges.length == n - 1 · 0 ≤ ai, bi < n · ai != bi · All the pairs (ai, bi) are distinct. · The given input is guaranteed to be a tree and there will be no repeated edges.

From brute force to the pattern: Running a BFS from every node to measure its height is O(n²). Trimming leaves inward, like a topological sort, finds the centre in O(n).

Spot it: Running a BFS from every node is O(n²). The best roots are the centre of the tree, and you can find the centre with a BFS that runs from the outside in.

Key insight: Multi-source BFS starting from all leaves. Peel off one layer of leaves per round. Nodes whose degree drops to 1 become the next layer. When 2 or fewer nodes remain, those are the centres (a tree has one or two of them).

Approach:

1. If n <= 2, every node is a centre.
2. Build adjacency sets (removal is easy) and put every leaf (degree 1) in a queue.
3. While more than 2 nodes remain, subtract the number of leaves in this layer, then remove each one.
4. Removing a leaf detaches it from its only neighbour. If that neighbour's degree drops to 1, it joins the next layer.
5. The 1 or 2 nodes left at the end are the answer.

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # With 1 or 2 nodes, every node is a centre.
        if n <= 2:
            answer = []
            for node in range(n):
                answer.append(node)
            return answer
        # graph[node] = set of its neighbours. A set makes removing one easy.
        graph = {}
        for node in range(n):
            graph[node] = set()
        for edge in edges:
            first = edge[0]
            second = edge[1]
            graph[first].add(second)
            graph[second].add(first)
        # The outer layer = every leaf (a node with exactly one neighbour).
        # append(x) adds at the back, popleft() takes from the front.
        leaves = deque()
        for node in range(n):
            if len(graph[node]) == 1:
                leaves.append(node)
        remaining = n
        # Peel one layer of leaves per round until only 1 or 2 nodes are left.
        while remaining > 2:
            layer_size = len(leaves)
            remaining = remaining - layer_size
            for _ in range(layer_size):
                leaf = leaves.popleft()
                # A leaf has exactly one neighbour. pop() takes it out of the set.
                neighbour = graph[leaf].pop()
                # Remove the edge from the neighbour's side too.
                graph[neighbour].remove(leaf)
                if len(graph[neighbour]) == 1:
                    # The neighbour has just become a leaf: it belongs to the next layer.
                    leaves.append(neighbour)
        # The nodes still in the queue are the centres.
        answer = []
        for node in leaves:
            answer.append(node)
        answer.sort()               # any order is accepted; sorted is easier to read
        return answer

What the code is doing, line by line:

1. With 1 or 2 nodes, every node is a centre, so we return [0] or [0, 1], built with a loop.
2. graph maps each node to a set of neighbours. Every edge [first, second] is added both ways because the tree is undirected.
3. The first leaves queue holds every node with exactly one neighbour: the outer layer of the tree.
4. remaining counts nodes not yet peeled. While more than 2 remain, we take a whole layer: layer_size is frozen and subtracted from remaining.
5. For each leaf, graph[leaf].pop() removes and returns its only neighbour, and graph[neighbour].remove(leaf) removes the edge from the other side.
6. If the neighbour is down to one neighbour, it has become a leaf of the smaller tree, so it joins the queue for the next layer.
7. When 2 or fewer nodes remain, the queue holds exactly those centres. We copy them into a list and sort it.

Dry run on n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] (answer [3, 4]). Node 3 has neighbours {0, 1, 2, 4}; node 4 has {3, 5}.

remaining = 2, so the loop stops and the answer is [3, 4].

Edge cases to test:

• n = 1 → [0].
• n = 2 → [0, 1].
• A star-shaped tree → the centre node.

Complexity: O(n) time and space.

Problem: Transform beginWord into endWord by changing one letter at a time, where every intermediate word must be in wordList. Return the number of words in the shortest sequence (including both ends), or 0.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ beginWord.length ≤ 10 · endWord.length == beginWord.length · 1 ≤ wordList.length ≤ 5000 · wordList[i].length == beginWord.length · beginWord, endWord, and wordList[i] consist of lowercase English letters. · beginWord != endWord · All the words in wordList are unique.

From brute force to the pattern: Comparing every pair of words to build the graph is O(n² · L). Generating neighbours with wildcard patterns plus BFS finds the shortest chain in O(n · L²).

Spot it: "shortest transformation sequence" + "one letter at a time" = BFS on an implicit graph of words.

Key insight: Comparing every pair of words is slow. Instead, bucket words by wildcard patterns: hot belongs to *ot, h*t, ho*. Two words are neighbours if they share a bucket. Empty each bucket after its first use, because later visits can't produce a shorter path.

Approach:

1. If endWord isn't in the word list, return 0.
2. Bucket every word by its wildcard patterns, e.g. hot → *ot, h*t, ho*.
3. BFS from (beginWord, 1). Pop a word and return its step count if it's endWord.
4. For each of its patterns, enqueue every unseen word in that bucket with steps + 1, then empty the bucket.
5. If the queue empties, return 0.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        if endWord not in words:
            return 0
        # buckets["h*t"] = every word that fits h?t, for example ["hot", "hit"].
        # Two words in the same bucket differ in exactly one letter.
        all_words = []
        for word in wordList:
            all_words.append(word)
        if beginWord not in words:
            all_words.append(beginWord)
        buckets = {}
        for word in all_words:
            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i + 1:]
                if pattern not in buckets:
                    buckets[pattern] = []
                buckets[pattern].append(word)
        seen = set()
        seen.add(beginWord)
        # The queue holds (word, number of words in the sequence so far).
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        queue.append((beginWord, 1))
        while len(queue) > 0:
            pair = queue.popleft()
            word = pair[0]
            steps = pair[1]
            if word == endWord:
                return steps
            for i in range(len(word)):
                pattern = word[:i] + "*" + word[i + 1:]
                for next_word in buckets[pattern]:
                    if next_word not in seen:
                        seen.add(next_word)
                        queue.append((next_word, steps + 1))
                # Empty the bucket: all its words are queued now, a later visit can't help.
                buckets[pattern] = []
        return 0

What the code is doing, line by line:

1. If endWord isn't in the word list, no sequence can end there: return 0.
2. all_words is the word list plus beginWord (if it isn't already in it).
3. For every word and every position i, word[:i] + "*" + word[i + 1:] replaces letter i with *. That pattern is the bucket key. If the key is new, we create an empty list first, then add the word.
4. BFS starts at (beginWord, 1), because the answer counts words, and the first word counts as 1.
5. Each pop is split into word = pair[0] and steps = pair[1]. If it's endWord, return steps.
6. For each of the word's patterns, every unseen word in that bucket is one letter away: mark it and queue it with steps + 1.
7. buckets[pattern] = [] empties the bucket. Everything in it is already queued, so looking at it again later would be wasted work.

Dry run on beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] (answer 5):

Edge cases to test:

• endWord not in the list → 0.
• beginWord one step from endWord → 2.
• Disconnected words → 0.

Complexity: O(N · L²) time (N words of length L, building the strings), O(N · L²) space. Bidirectional BFS (from both ends) speeds it up further in practice.

Problem: routes[i] is the loop of stops bus i visits. Starting at stop source, what's the fewest number of buses you must take to reach target? Return -1 if it's impossible.

Solve it on LeetCode ↗

Constraints: 1 ≤ routes.length ≤ 500. · 1 ≤ routes[i].length ≤ 10⁵ · All the values of routes[i] are unique. · sum(routes[i].length) ≤ 10⁵ · 0 ≤ routes[i][j] < 10⁶ · 0 ≤ source, target < 10⁶

From brute force to the pattern: BFS over stops, one stop per step, counts stops instead of buses and is slow. BFS by routes, marking each route as used once, gives the minimum number of buses in O(total stops).

Spot it: "fewest buses" = BFS, but the cost is per bus, not per stop. Each BFS level must be "one more bus".

Key insight: Expand a whole bus at once. From a stop, every unused bus through it reaches all of that bus's stops at cost +1. Mark buses as used so each route is expanded only once. Otherwise long routes make it O(stops²).

Approach:

1. If source == target, return 0.
2. Map each stop to the buses that serve it.
3. BFS over (stop, buses_taken), starting at (source, 0).
4. From a stop, take every bus not used yet: mark it used, and reach all of its stops at buses + 1.
5. Return as soon as one of those stops is the target. If the queue empties, return -1.

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        # stop_to_buses[stop] = list of the bus numbers that visit this stop.
        stop_to_buses = {}
        for bus in range(len(routes)):
            for stop in routes[bus]:
                if stop not in stop_to_buses:
                    stop_to_buses[stop] = []
                stop_to_buses[stop].append(bus)
        used_bus = set()            # buses we have already ridden
        seen_stop = set()           # stops we have already put in the queue
        seen_stop.add(source)
        # The queue holds (stop, buses taken to get here).
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        queue.append((source, 0))
        while len(queue) > 0:
            pair = queue.popleft()
            stop = pair[0]
            buses = pair[1]
            if stop not in stop_to_buses:
                continue            # no bus serves this stop
            for bus in stop_to_buses[stop]:
                if bus in used_bus:
                    continue        # each bus only needs to be ridden once
                used_bus.add(bus)
                # Riding this bus reaches ALL of its stops for one more bus.
                for next_stop in routes[bus]:
                    if next_stop == target:
                        return buses + 1
                    if next_stop not in seen_stop:
                        seen_stop.add(next_stop)
                        queue.append((next_stop, buses + 1))
        return -1

What the code is doing, line by line:

1. If we're already at the target, we need 0 buses.
2. stop_to_buses is built with two loops: for every bus number and every stop on its route, add the bus to that stop's list (creating the list the first time we see the stop).
3. used_bus remembers buses we've already ridden; seen_stop remembers stops already queued.
4. The queue holds (stop, buses). Each pop is split by indexing. A stop no bus visits is skipped.
5. For each unused bus at this stop, mark it used and walk its whole route. Every stop on it costs buses + 1. If one of them is the target, return right away; otherwise queue new stops.
6. Marking the bus as used is what keeps this fast: each route is scanned once, however many of its stops we later pop.

Dry run on routes = [[1,2,7],[3,6,7]], source = 1, target = 6 (answer 2). stop_to_buses = {1: [0], 2: [0], 7: [0, 1], 3: [1], 6: [1]}.

Edge cases to test:

• source == target → 0.
• The target is unreachable → −1.
• A stop shared by many routes.

Complexity: O(Σ len(routes[i])) time and space: each bus and each stop is expanded once.

Problem: Return the number of nodes on the shortest path from the root down to a leaf (a node with no children).

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [0, 10⁵]. · -1000 ≤ Node.val ≤ 1000

From brute force to the pattern: DFS must explore the whole tree to be sure of the minimum; it also has a trap: a node with one child is not a leaf. BFS stops at the shallowest leaf, often without visiting most of the tree.

Spot it: "minimum depth" is the shortest distance. BFS reaches shallow nodes first, so the first leaf it pops is the answer and it can stop early.

Approach:

1. If the tree is empty, return 0.
2. BFS with the queue holding (node, depth), starting at (root, 1).
3. Pop a node. If it has no children, return its depth.
4. Otherwise enqueue its children with depth + 1.

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        # The queue holds (node, depth of that node). The root has depth 1.
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        queue.append((root, 1))
        while len(queue) > 0:
            pair = queue.popleft()
            node = pair[0]
            depth = pair[1]
            # A leaf has no children. The first leaf we pop is the shallowest one.
            if node.left is None and node.right is None:
                return depth
            if node.left is not None:
                queue.append((node.left, depth + 1))
            if node.right is not None:
                queue.append((node.right, depth + 1))
        return 0                    # never reached for a non-empty tree

What the code is doing, line by line:

1. An empty tree has depth 0.
2. The queue holds (node, depth) pairs, starting with (root, 1).
3. Each pop is split into node = pair[0] and depth = pair[1].
4. If the node has no left and no right child, it is a leaf. BFS pops nodes in depth order, so the first leaf we meet is the shallowest: return its depth right away.
5. Otherwise queue each child that exists, one level deeper.

Dry run on root = [3,9,20,null,null,15,7] (answer 2):

Nodes 15 and 7 are never visited. That's the advantage over a DFS that would explore the whole tree.

Edge cases to test:

• An empty tree → 0.
• A chain of single children, e.g. [2, null, 3, null, 4] → 3 (not 1).
• A single node → 1.

Complexity: O(n) worst case, but it stops at the first leaf. O(w) space.

Problem: In an n × n grid of 0s (open) and 1s (blocked), find the length (number of cells) of the shortest path from the top-left to the bottom-right, moving in any of the 8 directions. Return -1 if there's no path.

Solve it on LeetCode ↗

Constraints: n == grid.length · n == grid[i].length · 1 ≤ n ≤ 100 · grid[i][j] is 0 or 1

From brute force to the pattern: DFS tries many paths and doesn't naturally give the shortest. BFS reaches each cell first along a shortest path: O(n²).

Spot it: "shortest clear path" where every move costs 1, so grid BFS.

Approach:

1. If the start or end cell is blocked, return -1.
2. Enqueue (0, 0, 1), since the path length counts cells, and mark the start (set it to 1).
3. Pop a cell. If it's the bottom-right, return its distance.
4. For all 8 neighbours that are in bounds and open: mark them, then enqueue them with distance + 1.

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        size = len(grid)
        last = size - 1
        # A blocked start or a blocked end means there is no path at all.
        if grid[0][0] == 1 or grid[last][last] == 1:
            return -1
        # The queue holds (row, col, cells on the path so far). The start counts as 1.
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        queue.append((0, 0, 1))
        grid[0][0] = 1              # reuse the grid as "visited": 1 = blocked or visited
        while len(queue) > 0:
            item = queue.popleft()
            row = item[0]
            col = item[1]
            length = item[2]
            if row == last and col == last:
                return length
            # All 8 directions: the row and the col each change by -1, 0 or +1.
            for row_change in [-1, 0, 1]:
                for col_change in [-1, 0, 1]:
                    new_row = row + row_change
                    new_col = col + col_change
                    # Skip cells outside the grid.
                    if new_row < 0 or new_row >= size or new_col < 0 or new_col >= size:
                        continue
                    if grid[new_row][new_col] == 0:
                        grid[new_row][new_col] = 1      # mark on enqueue
                        queue.append((new_row, new_col, length + 1))
        return -1

What the code is doing, line by line:

1. size is the grid width, last = size - 1 the index of the last row/column.
2. If the start or the end cell is blocked, return -1 immediately.
3. The queue holds (row, col, length), where length counts cells on the path, so the start is 1. Setting grid[0][0] = 1 marks it as visited (we reuse the grid instead of a separate set).
4. Each pop is split into row, col, length by indexing. Popping the bottom-right cell means we're done.
5. The two nested loops over [-1, 0, 1] try all 8 neighbours (the "no move" case lands on the current cell, which is already marked, so it's skipped).
6. Cells outside the grid are skipped. An open cell (0) is marked 1 and queued with length + 1.

Dry run on grid = [[0,0,0],[1,1,0],[1,1,0]] (answer 4):

Edge cases to test:

• The start or end cell is 1 → −1.
• A 1 × 1 grid with a 0 → 1.
• Diagonal shortcuts.

Complexity: O(n²) time and space.

Problem: For every cell of a 0/1 matrix, return the distance to the nearest 0 (moving up, down, left or right).

Solve it on LeetCode ↗

Constraints: m == mat.length · n == mat[i].length · 1 ≤ m, n ≤ 10⁴ · 1 ≤ m * n ≤ 10⁴ · mat[i][j] is either 0 or 1. · There is at least one 0 in mat.

From brute force to the pattern: A BFS per cell is O((r · c)²). One multi-source BFS from every zero computes every distance in O(r · c) (a two-pass DP also works).

Spot it: "distance to the nearest X" for every cell is multi-source BFS starting from all the 0s at once.

Approach:

1. Make dist filled with -1, meaning unknown.
2. Every 0 cell gets dist = 0 and goes into the queue.
3. Pop a cell. Each neighbour with unknown distance gets dist[cell] + 1 and is enqueued.
4. Each cell is first reached by its nearest 0, so it's final the moment it's set.

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows = len(mat)
        cols = len(mat[0])
        # dist starts full of -1, which means "not reached yet".
        dist = []
        for row in range(rows):
            dist_row = [-1] * cols      # a list holding cols copies of -1
            dist.append(dist_row)
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        # Every 0 is a source at distance 0.
        for row in range(rows):
            for col in range(cols):
                if mat[row][col] == 0:
                    dist[row][col] = 0
                    queue.append((row, col))
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while len(queue) > 0:
            cell = queue.popleft()
            row = cell[0]
            col = cell[1]
            for direction in directions:
                new_row = row + direction[0]
                new_col = col + direction[1]
                if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= cols:
                    continue
                if dist[new_row][new_col] == -1:
                    # The first time a cell is reached, it is by its nearest 0.
                    dist[new_row][new_col] = dist[row][col] + 1
                    queue.append((new_row, new_col))
        return dist

What the code is doing, line by line:

1. dist is built row by row. Each row is [-1] * cols, a list of cols copies of -1, meaning "not reached yet".
2. The double loop finds every 0. Each gets dist = 0 and goes into the queue: all zeros are sources (multi-source BFS).
3. Each pop is split into row and col. For each of the 4 neighbours inside the grid that is still -1, its distance is the popped cell's distance + 1, and it's queued.
4. Because all zeros started together, the first ripple to reach a cell comes from its nearest zero, so a cell's distance never needs to change once set.

Dry run on mat = [[0,0,0],[0,1,0],[1,1,1]] (answer [[0,0,0],[0,1,0],[1,2,1]]). Starting queue: the five zeros (0,0), (0,1), (0,2), (1,0), (1,2).

Edge cases to test:

• A single 0 in a corner.
• Every cell is 0 → all distances 0.
• Large grids (avoid the per-cell BFS).

Complexity: O(R·C) time and space.

Problem: The grid holds -1 (wall), 0 (gate) and INF = 2147483647 (empty room). Fill each empty room in place with the distance to its nearest gate, and leave INF where no gate is reachable.

Solve it on LeetCode ↗ (Premium)

Constraints: m == rooms.length, n == rooms[i].length · 1 ≤ m, n ≤ 250 · rooms[i][j] is -1, 0, or 2³¹ − 1

From brute force to the pattern: A BFS from every empty room is O((r · c)²). Starting from all gates together means each room is reached first by its nearest gate: O(r · c).

Spot it: "nearest gate" for every room is multi-source BFS from all the gates.

Approach:

1. Enqueue every gate.
2. Pop a cell. For each 4-neighbour that's still INF, set it to the current cell's value + 1 and enqueue it.
3. Walls are never INF and gates are 0, so the == INF check skips both. It also acts as the visited check.

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        INF = 2147483647            # the value LeetCode uses for an empty room
        if len(rooms) == 0:
            return
        rows = len(rooms)
        cols = len(rooms[0])
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        # Every gate (0) is a source.
        for row in range(rows):
            for col in range(cols):
                if rooms[row][col] == 0:
                    queue.append((row, col))
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while len(queue) > 0:
            cell = queue.popleft()
            row = cell[0]
            col = cell[1]
            for direction in directions:
                new_row = row + direction[0]
                new_col = col + direction[1]
                if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= cols:
                    continue
                # Only empty, unvisited rooms are still INF (walls are -1, gates are 0).
                if rooms[new_row][new_col] == INF:
                    rooms[new_row][new_col] = rooms[row][col] + 1
                    queue.append((new_row, new_col))

What the code is doing, line by line:

1. INF is the special "empty room" value from the problem. An empty grid has nothing to do.
2. The double loop queues every gate (value 0). They are all sources at distance 0.
3. Each pop is split into row and col. Out-of-grid neighbours are skipped.
4. Only a neighbour that is still INF is updated. Walls (-1) and gates (0) never equal INF, and a room we've already filled no longer does either, so this one check means "unvisited empty room".
5. The room gets the popped cell's value + 1 and is queued. The grid is changed in place, so nothing is returned.

Dry run on the LeetCode example (I = INF): [[I,-1,0,I],[I,I,I,-1],[I,-1,I,-1],[0,-1,I,I]]. Starting queue: gates (0,2), (3,0).

Final grid: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]].

Edge cases to test:

• No gates → nothing changes.
• Rooms walled off from every gate stay INF.
• Several gates at the same distance.

Complexity: O(R·C) time and space.

Problem: A maze has '.' (open) and '+' (wall) cells. From entrance, find the fewest steps to any open cell on the border (an exit). The entrance itself doesn't count as an exit. Return -1 if there's none.

Solve it on LeetCode ↗

Constraints: maze.length == m · maze[i].length == n · 1 ≤ m, n ≤ 100 · maze[i][j] is either '.' or '+'. · entrance.length == 2 · 0 ≤ entrancerow < m · 0 ≤ entrancecol < n · entrance will always be an empty cell.

From brute force to the pattern: DFS doesn't give the shortest distance without exploring everything. BFS finds the nearest exit in O(r · c).

Spot it: "fewest steps" on a grid is BFS. The target is any border cell, so test for it when you enqueue.

Approach:

1. Mark the entrance as a wall (visited) and enqueue (r, c, 0).
2. Pop a cell and look at its 4 open, in-bounds neighbours.
3. If a neighbour is on the border, return d + 1 right away.
4. Otherwise mark it and enqueue it with d + 1. If the queue empties, return -1.

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        rows = len(maze)
        cols = len(maze[0])
        start_row = entrance[0]
        start_col = entrance[1]
        # Turn the entrance into a wall: it is visited, and it can't count as an exit.
        maze[start_row][start_col] = "+"
        # The queue holds (row, col, steps taken so far).
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        queue.append((start_row, start_col, 0))
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while len(queue) > 0:
            item = queue.popleft()
            row = item[0]
            col = item[1]
            steps = item[2]
            for direction in directions:
                new_row = row + direction[0]
                new_col = col + direction[1]
                if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= cols:
                    continue
                if maze[new_row][new_col] != ".":
                    continue        # a wall, or already visited
                # An open cell on the border is an exit. The first one found is the nearest.
                if new_row == 0 or new_row == rows - 1 or new_col == 0 or new_col == cols - 1:
                    return steps + 1
                maze[new_row][new_col] = "+"        # mark on enqueue
                queue.append((new_row, new_col, steps + 1))
        return -1

What the code is doing, line by line:

1. start_row and start_col are read from entrance by indexing.
2. The entrance is overwritten with "+". That marks it visited, and it also stops it from being counted as an exit later.
3. The queue holds (row, col, steps), starting with 0 steps.
4. Each pop is split by indexing. Neighbours outside the grid, walls, and visited cells are skipped with continue.
5. If an open neighbour lies on the border (first/last row or column), it's an exit. BFS reaches cells in order of distance, so return steps + 1 right away.
6. Otherwise mark it and queue it with steps + 1. An empty queue means there's no exit: return -1.

Dry run on maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] (answer 1):

Edge cases to test:

• The entrance is on the border (it doesn't count as an exit).
• No reachable exit → −1.
• A 1 × 1 maze → −1.

Complexity: O(R·C) time and space.

Problem: In a connected undirected graph, return the length of the shortest walk that visits every node. You may start and end anywhere, and revisit nodes and edges.

Solve it on LeetCode ↗

Constraints: n == graph.length · 1 ≤ n ≤ 12 · 0 ≤ graph[i].length < n · graph[i] does not contain i. · If graph[a] contains b, then graph[b] contains a. · The input graph is always connected.

From brute force to the pattern: Trying every order of visiting nodes is O(n!). BFS over the n · 2ⁿ states finds the shortest walk; that's fine for n ≤ 12.

Spot it: "shortest" with unit edges means BFS, but the position alone isn't enough state. The real state is (node, set of nodes visited so far), stored as a bitmask. Since you can start anywhere, it's multi-source.

Approach:

1. The goal mask is full = (1 << n) - 1, with every bit set.
2. Seed the queue with (u, 1 << u, 0) for every node u (multi-source).
3. Pop a state. If its mask is full, return its distance.
4. For each neighbour v, the new state is (v, mask | 1 << v). Enqueue it if that state hasn't been seen.

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        node_count = len(graph)
        # A bitmask stores a set of nodes in one integer: bit u is 1 if node u is visited.
        # full has every bit set, which means "all nodes visited".
        full = (1 << node_count) - 1
        # The queue holds (node, mask, steps). seen holds (node, mask) states.
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        seen = set()
        # We may start anywhere: every node is a source that has visited only itself.
        for node in range(node_count):
            start_mask = 1 << node
            queue.append((node, start_mask, 0))
            seen.add((node, start_mask))
        while len(queue) > 0:
            item = queue.popleft()
            node = item[0]
            mask = item[1]
            steps = item[2]
            if mask == full:
                return steps
            for neighbour in graph[node]:
                # Walk to neighbour and add it to the visited set (bitwise OR sets its bit).
                new_mask = mask | (1 << neighbour)
                state = (neighbour, new_mask)
                if state not in seen:       # same node + same visited set = same future
                    seen.add(state)
                    queue.append((neighbour, new_mask, steps + 1))
        return 0

What the code is doing, line by line:

1. A bitmask is an integer used as a set: bit u is 1 when node u has been visited. 1 << u is the number with only bit u set. full = (1 << node_count) - 1 has all bits set (for 4 nodes, binary 1111 = 15).
2. The seeding loop puts every node in the queue as (node, only-itself mask, 0 steps), because we may start anywhere (multi-source BFS). The same (node, mask) pairs go into seen.
3. Each pop is split into node, mask, steps. If the mask is full, every node is visited: return steps.
4. Moving to a neighbour gives new_mask = mask | (1 << neighbour) (the | turns the neighbour's bit on). The state (neighbour, new_mask) is queued only if it's new: standing on the same node having visited the same set means the future is identical.

Dry run on the star graph [[1,2,3],[0],[0],[0]] (answer 4). Masks are shown in decimal (full = 15):

Edge cases to test:

• A single node → 0.
• Revisiting nodes is allowed (and sometimes needed).
• A path graph vs a star graph.

Complexity: O(2n · n²) time and O(2n · n) space. That's fine because n ≤ 12.

Problem: Move up, down, left or right through a 0/1 grid from the top-left to the bottom-right. You may remove at most k obstacles (1s). Return the minimum number of steps, or -1.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 40 · 1 ≤ k ≤ m * n · grid[i][j] is either 0 or 1. · grid[0][0] == grid[m - 1][n - 1] == 0

From brute force to the pattern: Plain BFS ignores removals; DFS over every choice is exponential. BFS over (cell, removals left) states finds the shortest path in O(r · c · k).

Spot it: "minimum steps" means BFS, but the same cell reached with more removals left is a better state. So the state is (r, c, removals_left).

Approach:

1. Shortcut: if k ≥ R + C - 2, you can walk straight through anything, so return R + C - 2.
2. BFS over (r, c, left, steps), starting at (0, 0, k, 0).
3. Pop a state. If it's the bottom-right cell, return steps.
4. For each in-bounds neighbour, nl = left - grid[nr][nc] (stepping on an obstacle uses one removal). If nl ≥ 0 and the state is unseen, enqueue it.

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        rows = len(grid)
        cols = len(grid[0])
        # A straight walk takes rows + cols - 2 steps. With that many removals,
        # nothing can block us, so that is the answer.
        if k >= rows + cols - 2:
            return rows + cols - 2
        # The queue holds (row, col, removals left, steps).
        # append(x) adds at the back, popleft() takes from the front.
        queue = deque()
        queue.append((0, 0, k, 0))
        # seen holds (row, col, removals left). The same cell with more removals
        # left is a different (better) state, so it gets its own entry.
        seen = set()
        seen.add((0, 0, k))
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while len(queue) > 0:
            item = queue.popleft()
            row = item[0]
            col = item[1]
            left = item[2]
            steps = item[3]
            if row == rows - 1 and col == cols - 1:
                return steps
            for direction in directions:
                new_row = row + direction[0]
                new_col = col + direction[1]
                if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= cols:
                    continue
                # An obstacle (1) uses up one removal; an open cell (0) costs nothing.
                new_left = left - grid[new_row][new_col]
                if new_left >= 0 and (new_row, new_col, new_left) not in seen:
                    seen.add((new_row, new_col, new_left))
                    queue.append((new_row, new_col, new_left, steps + 1))
        return -1

What the code is doing, line by line:

1. The shortest possible walk is rows + cols - 2 steps (only down and right). If k is at least that, we can remove anything in the way, so return it.
2. The queue holds (row, col, left, steps), where left is how many removals we still have. seen stores (row, col, left): arriving at the same cell with a different number of removals left is a different state.
3. Each pop is split into four variables by indexing. Reaching the bottom-right cell returns steps.
4. For each neighbour inside the grid, new_left = left - grid[new_row][new_col]: a 1 (obstacle) costs one removal, a 0 costs nothing.
5. If new_left is still 0 or more and that state is new, mark it and queue it with steps + 1. An empty queue means we can't get through: return -1.

Dry run on grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1 (answer 6). States are (row, col, left), grouped by BFS level:

The winning path goes down the left side, removing the obstacle at (1,0), then along the bottom row.

Edge cases to test:

• k ≥ r + c − 3 → the Manhattan distance (you can go straight through).
• A 1 × 1 grid → 0.
• Unreachable even with removals → −1.

Complexity: O(R·C·k) time and space.

Problem: Return the average value of the nodes on each level of the tree, from top to bottom.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [1, 10⁴]. · -2³¹ ≤ Node.val ≤ 2³¹ - 1

From brute force to the pattern: DFS collecting (sum, count) per depth also works in O(n). BFS gives the levels directly in order.

Spot it: "Per level" → BFS with a queue, processing exactly one level per round (len(queue) nodes).

Approach:

1. Put the root in a queue.
2. While the queue isn't empty: the current level is the len(queue) nodes in it right now.
3. Pop each of them, add its value to a running total, and push its children (they form the next level).
4. Append total / level_size.

from collections import deque

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        averages = []
        queue = deque([root])
        while queue:
            level_size = len(queue)      # nodes on the current level
            total = 0
            for _ in range(level_size):
                node = queue.popleft()
                total = total + node.val
                # children belong to the next level
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            averages.append(total / level_size)
        return averages

What the code is doing, line by line:

1. deque([root]): a double-ended queue; popleft() is O(1) (a list's pop(0) is O(n)).
2. level_size = len(queue): measured before the loop, so children pushed during it wait for the next round.
3. for _ in range(level_size): pop exactly the nodes of this level and add their values.
4. queue.append(node.left) / node.right: enqueue the next level.
5. total / level_size: / is true division, so 29 / 2 gives 14.5.

Dry run on the example:

root = [3, 9, 20, null, null, 15, 7] (LeetCode Example 1). Returns [3.0, 14.5, 11.0].

Edge cases to test:

• A single node.
• Large values (Python's integers don't overflow).
• Uneven levels.

Complexity: O(n) time, O(w) space for the queue (w = the widest level).

Problem: Each node has an extra next pointer. Point every node's next at the node directly to its right on the same level, or None if it is the last one. The tree is not necessarily perfect.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 6000]. · -100 ≤ Node.val ≤ 100

From brute force to the pattern: Collecting each level into a list and linking it is O(n) time and space. BFS links as it goes; the follow-up technique walks each level using its own next pointers with O(1) extra space.

Spot it: "Same level, left to right" is exactly the order BFS pops nodes. Within one level, each popped node's next is simply the following node in the queue.

Key insight: A follow-up asks for O(1) extra space: walk each level along the next pointers you already built while linking the level below with a dummy head. The BFS version below is the clearest starting point.

Approach:

1. BFS with a queue, one level per round.
2. Pop the level's nodes in order, remembering the previously popped node prev.
3. Set prev.next = node for every node after the first; the last node keeps next = None.
4. Push each node's children for the next level.

from collections import deque

class Solution:
    def connect(self, root: "Node") -> "Node":
        if root is None:
            return None
        queue = deque([root])
        while queue:
            level_size = len(queue)
            prev = None
            for _ in range(level_size):
                node = queue.popleft()
                if prev is not None:
                    # the node popped before this one is its left neighbour
                    prev.next = node
                prev = node
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            # the last node of the level keeps next = None
        return root

What the code is doing, line by line:

1. if root is None: return None: nothing to connect.
2. level_size = len(queue): the number of nodes on this level.
3. prev = None at the start of every level, so the first node of a level is never linked from the previous level's last node.
4. if prev is not None: prev.next = node: chain the level together in the order the queue gives us, which is left to right.
5. Children are appended left before right, which keeps the next level in left-to-right order too.

Dry run on the example:

root = [1, 2, 3, 4, 5, null, 7] (LeetCode Example 1). Result levels: 1 → None, 2 → 3 → None, 4 → 5 → 7 → None.

Edge cases to test:

• An empty tree.
• Missing children in the middle of a level.
• The last node of each level points to None.

Complexity: O(n) time, O(w) queue space (O(1) with the follow-up technique).

Problem: A gene is an 8-character string of A, C, G, T. One mutation changes one character, and every intermediate gene must be in bank. Return the minimum number of mutations from startGene to endGene, or -1 if impossible.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ bank.length ≤ 10 · startGene.length == endGene.length == bank[i].length == 8 · startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

From brute force to the pattern: DFS doesn't give the minimum number of mutations. BFS finds the shortest chain in O(b · 8 · 4).

Spot it: "Minimum number of single changes" between states → each gene is a node, each valid mutation an edge, and all edges cost 1. Shortest path in an unweighted graph = BFS.

Approach:

1. Put bank in a set for O(1) membership checks. If endGene isn't in it, return -1 straight away.
2. BFS from startGene with a step count, plus a visited set.
3. For each popped gene, try every position × every other letter (8 × 3 = 24 mutations). Queue the ones that are in the bank and not yet visited.
4. The first time endGene is popped, its step count is the minimum.

from collections import deque

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        valid = set(bank)
        if endGene not in valid:
            return -1
        queue = deque([(startGene, 0)])
        visited = {startGene}
        while queue:
            gene, steps = queue.popleft()
            if gene == endGene:
                return steps
            # every gene that differs from this one in exactly one position
            for i in range(len(gene)):
                for ch in "ACGT":
                    if ch == gene[i]:
                        continue
                    mutated = gene[:i] + ch + gene[i + 1:]
                    if mutated in valid and mutated not in visited:
                        visited.add(mutated)
                        queue.append((mutated, steps + 1))
        return -1

What the code is doing, line by line:

1. valid = set(bank): membership tests in O(1). If the target isn't in the bank, it can never be reached.
2. queue = deque([(startGene, 0)]): each entry carries its distance from the start.
3. visited = {startGene}: mark genes when they are queued, so the same gene is never queued twice.
4. if gene == endGene: return steps: BFS pops genes in order of distance, so the first time we pop the target is the shortest route.
5. mutated = gene[:i] + ch + gene[i + 1:]: copy the gene with position i replaced by ch.
6. return -1: the queue emptied without reaching the target.

Dry run on the example:

startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"] (LeetCode Example 2). Returns 2.

Edge cases to test:

• endGene not in the bank → −1.
• startGene == endGene → 0.
• An empty bank.

Complexity: O(b · L · 4) time, where b is the bank size and L = 8; O(b) space for the set, queue and visited.

Problem: An n × n board is numbered 1..n² starting at the bottom-left, alternating direction on every row (boustrophedon). Each move, roll a die and go 1–6 squares forward; if you land on a snake or ladder (board[r][c] != -1), you must take it to that square. Return the fewest moves to reach n², or -1.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == board.length == board[i].length · 2 ≤ n ≤ 20 · board[i][j] is either -1 or in the range [1, n²]. · The squares labeled 1 and n² are not the starting points of any snake or ladder.

From brute force to the pattern: Trying every sequence of rolls is exponential. BFS over the n² squares finds the fewest moves in O(n²).

Spot it: "Fewest moves" where every move costs 1 → BFS over squares. Each square has up to six neighbours (s + 1 .. s + 6, then follow a snake/ladder).

Key insight: Convert a square number to its cell: row_from_bottom = (s − 1) // n, col = (s − 1) % n, and flip col on odd rows from the bottom because those rows run right-to-left. The real row index is n − 1 − row_from_bottom.

Approach:

1. Write cell(s) to turn a square number into (row, col).
2. BFS from square 1 with move count 0; mark squares as visited when queued.
3. For each popped square, try s + 1 .. min(s + 6, n²). If that cell has a snake or ladder, jump to its destination.
4. Return the move count when n² is reached; -1 if the queue empties.

from collections import deque

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)

        def cell(square):
            # squares count from the bottom-left, zig-zagging every row
            row_from_bottom = (square - 1) // n
            col = (square - 1) % n
            if row_from_bottom % 2 == 1:
                col = n - 1 - col          # odd rows (from the bottom) run right-to-left
            return n - 1 - row_from_bottom, col

        target = n * n
        queue = deque([(1, 0)])            # (square, moves taken)
        visited = {1}
        while queue:
            square, moves = queue.popleft()
            if square == target:
                return moves
            for step in range(1, 7):
                nxt = square + step
                if nxt > target:
                    break
                r, c = cell(nxt)
                if board[r][c] != -1:
                    nxt = board[r][c]      # forced to take the snake or ladder
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, moves + 1))
        return -1

What the code is doing, line by line:

1. def cell(square): row 0 of board is the top, but square 1 is at the bottom, hence n - 1 - row_from_bottom.
2. if row_from_bottom % 2 == 1: col = n - 1 - col: rows alternate direction, so every second row is mirrored.
3. queue = deque([(1, 0)]): start on square 1 having made 0 moves.
4. for step in range(1, 7): the six die faces. if nxt > target: break: you can't move past the last square.
5. if board[r][c] != -1: nxt = board[r][c]: a snake or ladder is mandatory, so the neighbour is its destination.
6. if nxt not in visited: BFS reaches each square first by the fewest moves, so later visits are useless.

Dry run on the example:

LeetCode Example 1, a 6 × 6 board with a ladder 2 → 15, a ladder 14 → 35 and a snake 17 → 13. Returns 4 (1 → 2↑15 → 17↓13 → 14↑35 → 36). Each row is one BFS level.

Rolling a 2 from square 1 lands on the ladder, which is why 15 is reached in one move and 2 never appears. Likewise 17 is a snake down to 13, and 14 is a ladder up to 35, which is then one roll from 36.

Edge cases to test:

• A ladder or snake on square 1 is never taken (you start there).
• You can't chain a snake/ladder into another in the same move.
• The target unreachable → −1.

Complexity: O(n²) time (each square is queued at most once, with 6 tries), O(n²) space.

Problem: Return the values of all nodes at distance exactly k from the target node (any order).

Solve it on LeetCode ↗

Constraints: The number of nodes in the tree is in the range [1, 500]. · 0 ≤ Node.val ≤ 500 · All the values Node.val are unique. · target is the value of one of the nodes in the tree. · 0 ≤ k ≤ 1000

From brute force to the pattern: Computing the distance from target to every node via LCA separately is O(n · h); one BFS on the parent-linked tree is O(n).

Spot it: Distance can go up through parents as well as down. Record each node's parent (one DFS), then treat the tree as an undirected graph and run BFS from target for k layers.

Why not another pattern? Only searching down from target misses nodes reached through its ancestors.

Approach:

1. DFS from the root to fill parent[node].
2. BFS from target with a visited set, using left, right and parent as neighbours.
3. After k layers, the queue holds exactly the answer.

from collections import deque

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        parent = {root: None}
        stack = [root]
        while stack:
            node = stack.pop()
            for child in (node.left, node.right):
                if child:
                    parent[child] = node  # lets BFS walk upward too
                    stack.append(child)
        queue = deque([target])
        seen = {target}
        for _ in range(k):  # expand exactly k layers
            for _ in range(len(queue)):
                node = queue.popleft()
                for nb in (node.left, node.right, parent[node]):
                    if nb and nb not in seen:
                        seen.add(nb)
                        queue.append(nb)
        return [node.val for node in queue]  # everything exactly k away

What the code is doing, line by line:

1. The parent map turns each node's neighbours into left, right and parent.
2. BFS layer d holds exactly the nodes at distance d from target.
3. seen stops the search from walking back the way it came.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 0 → [target.val].
• k larger than the tree → [].
• Target is the root.

Complexity: O(n) time and space.

Problem: A binary grid has exactly two islands. Return the fewest 0s to flip to connect them.

Solve it on LeetCode ↗

Constraints: n == grid.length == grid[i].length · 2 ≤ n ≤ 100 · grid[i][j] is either 0 or 1. · There are exactly two islands in grid.

From brute force to the pattern: BFS from each cell of the first island separately is O(n⁴); multi-source BFS is O(n²).

Spot it: The answer is the shortest water distance between the islands. Find all cells of one island (DFS), then expand from all of them at once (multi-source BFS); the layer at which another 1 is touched is the answer.

Why not another pattern? BFS from every cell of island one separately is O(n⁴).

Approach:

1. Find any 1; flood-fill its island, marking cells as 2 and queueing them.
2. BFS layer by layer over 0s, marking visited water as 2.
3. When a neighbour is a 1 (the other island), return the current layer count.

from collections import deque

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        start = next((r, c) for r in range(n) for c in range(n) if grid[r][c] == 1)
        queue = deque()
        stack = [start]
        grid[start[0]][start[1]] = 2
        while stack:  # mark the first island
            r, c = stack.pop()
            queue.append((r, c))
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    stack.append((nr, nc))
        flips = 0
        while queue:  # grow outward from the whole island at once
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] == 1:
                            return flips  # touched the second island
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = 2  # water reached: one more flip
                            queue.append((nr, nc))
            flips += 1
        return -1

What the code is doing, line by line:

1. Marking the first island as 2 separates it from the second (still 1).
2. All of the first island starts the BFS together, so layer d holds the water cells at distance d.
3. Touching a 1 while expanding layer flips means flips water cells lie between the islands.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Islands touching diagonally (still need 1 flip).
• Islands one cell apart.
• Large islands far apart.

Complexity: O(n²) time and space.

Problem: In a directed graph with red and blue edges, return for each node the shortest path length from 0 whose edge colours alternate (−1 if none).

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 100 · 0 ≤ redEdges.length, blueEdges.length ≤ 400 · redEdges[i].length == blueEdges[j].length == 2 · 0 ≤ ai, bi, uj, vj < n

From brute force to the pattern: Enumerating alternating paths with DFS is exponential; BFS over 2n states is linear.

Spot it: Which edges you may take next depends on the colour you just used, so the BFS state is (node, last colour); each node can be reached twice.

Why not another pattern? A BFS on nodes alone marks a node visited after one colour and wrongly blocks the other colour's route.

Approach:

1. Adjacency lists per colour.
2. BFS from (0, red) and (0, blue) at distance 0.
3. From (u, colour) follow edges of the other colour to (v, other); the first time a node is reached, record its distance.

from collections import deque

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        adj = [[[] for _ in range(n)] for _ in range(2)]  # adj[0] red, adj[1] blue
        for a, b in redEdges:
            adj[0][a].append(b)
        for a, b in blueEdges:
            adj[1][a].append(b)
        answer = [-1] * n
        answer[0] = 0
        queue = deque([(0, 0, 0), (0, 1, 0)])  # node, colour of the last edge, distance
        seen = {(0, 0), (0, 1)}
        while queue:
            u, colour, d = queue.popleft()
            nxt_colour = 1 - colour  # must switch colour
            for v in adj[nxt_colour][u]:
                if (v, nxt_colour) not in seen:
                    seen.add((v, nxt_colour))
                    if answer[v] == -1:
                        answer[v] = d + 1  # first arrival is the shortest
                    queue.append((v, nxt_colour, d + 1))
        return answer

What the code is doing, line by line:

1. Starting with both colours at node 0 lets the first edge be either red or blue.
2. Each state follows only edges of the opposite colour.
3. BFS reaches states in increasing distance, so the first arrival at a node (in either colour) is its answer.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Self-loops and parallel edges of both colours.
• Unreachable nodes → −1.
• Node 0 → 0.

Complexity: O(n + e) time and space.

Problem: From index i you may step to i ± 1, or, if nums[i] is a prime p, teleport to any j with nums[j] % p == 0. Return the minimum jumps from 0 to n − 1.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁶

From brute force to the pattern: Scanning all indices for each prime you land on is O(n²). Grouping by prime factor and clearing groups keeps BFS near-linear.

Spot it: Fewest jumps → BFS. Teleport edges are dense, like Jump Game IV: group indices by each prime factor of their value (sieve of smallest prime factors), and after a prime's group is used once, clear it.

Why not another pattern? Checking nums[j] % p for every j each time a prime is reached is O(n²).

Approach:

1. Sieve the smallest prime factor up to max(nums).
2. For each index, add it to groups[p] for every distinct prime p dividing nums[j].
3. BFS from 0 with neighbours i ± 1, plus groups[nums[i]] when nums[i] is prime; clear that group after use.

from collections import defaultdict, deque

class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        top = max(nums)
        spf = list(range(top + 1))  # smallest prime factor of each number
        for p in range(2, int(top ** 0.5) + 1):
            if spf[p] == p:
                for m in range(p * p, top + 1, p):
                    if spf[m] == m:
                        spf[m] = p
        groups = defaultdict(list)  # prime -> indices whose value it divides
        for j, x in enumerate(nums):
            while x > 1:
                p = spf[x]
                groups[p].append(j)
                while x % p == 0:
                    x //= p
        dist = [-1] * n
        dist[0] = 0
        queue = deque([0])
        while queue:
            i = queue.popleft()
            if i == n - 1:
                return dist[i]
            targets = [i - 1, i + 1]
            x = nums[i]
            if x > 1 and spf[x] == x:  # nums[i] is prime: teleport
                targets += groups[x]
                groups[x] = []  # these indices are queued now; never scan them again
            for j in targets:
                if 0 <= j < n and dist[j] == -1:
                    dist[j] = dist[i] + 1
                    queue.append(j)
        return -1

What the code is doing, line by line:

1. The sieve gives each number's smallest prime factor, which lets us factor every value quickly.
2. groups[p] lists exactly the indices a prime p can teleport to.
3. After one teleport from any index with value p, all those targets are queued, so the group is emptied.
4. BFS distances are the minimum jump counts.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 0.
• Value 1 (not prime, divisible by nothing).
• Many copies of the same prime.

Complexity: O(M log log M + n log M) time for the sieve and factoring (M = max(nums)), O(M + n log M) space.

Problem: Return all shortest transformation sequences from beginWord to endWord, changing one letter at a time through words of wordList.

Solve it on LeetCode ↗

Constraints: 1 ≤ beginWord.length ≤ 5 · endWord.length == beginWord.length · 1 ≤ wordList.length ≤ 500 · wordList[i].length == beginWord.length · beginWord, endWord, and wordList[i] consist of lowercase English letters. · beginWord != endWord · All the words in wordList are unique. · The sum of all shortest transformation sequences does not exceed 10⁵.

From brute force to the pattern: DFS over every transformation sequence is exponential. BFS with parent sets keeps only shortest-path edges.

Spot it: Shortest → BFS. All shortest paths → during BFS, record for each word every word on the previous layer that leads to it (its parents), and only expand words not seen in earlier layers. Then backtrack from endWord through the parents.

Why not another pattern? DFS over all paths explores exponentially many long paths; storing full paths in the BFS queue blows up memory.

Approach:

1. BFS from beginWord one layer at a time; remove the whole layer from the word set before expanding it.
2. For each word, try all one-letter changes; any that is in the set gets this word added to its parents.
3. Stop after the layer that reaches endWord.
4. Backtrack from endWord to beginWord through parents, building each path in reverse.

from collections import defaultdict

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        words = set(wordList)
        if endWord not in words:
            return []
        parents = defaultdict(set)  # word -> words one layer earlier that lead to it
        layer = {beginWord}
        words.discard(beginWord)
        found = False
        while layer and not found:
            nxt = defaultdict(set)
            for word in layer:
                for i in range(len(word)):
                    for ch in "abcdefghijklmnopqrstuvwxyz":
                        cand = word[:i] + ch + word[i + 1:]
                        if cand in words:
                            nxt[cand].add(word)  # one more shortest way into cand
                            if cand == endWord:
                                found = True
            words -= nxt.keys()  # words reached now can't appear on a later layer
            for w, ps in nxt.items():
                parents[w] |= ps
            layer = set(nxt)
        if not found:
            return []
        ladders = []
        path = [endWord]

        def back(word):
            if word == beginWord:
                ladders.append(path[::-1])  # reached the start: one full ladder
                return
            for p in parents[word]:
                path.append(p)
                back(p)
                path.pop()

        back(endWord)
        return ladders

What the code is doing, line by line:

1. Words are removed from the set only after a whole layer is processed, so several words of the same layer can all become parents of one word.
2. A word reached in an earlier layer is never used again, which keeps every recorded edge on a shortest path.
3. Backtracking from endWord follows only shortest-path edges, so every path found has minimum length.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• endWord not in the list → [].
• Several shortest ladders sharing words.
• beginWord one step from endWord.

Complexity: O(N · L · 26) for the BFS (N words of length L) plus the size of the output for backtracking.

Problem: In a grid with walls, keys a–f and locks A–F, return the fewest moves from @ to collect every key, or −1.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 30 · grid[i][j] is either an English letter, '.', '#', or '@'. · There is exactly one '@' in the grid. · The number of keys in the grid is in the range [1, 6]. · Each key in the grid is unique. · Each key in the grid has a matching lock.

From brute force to the pattern: Trying every key order (K!) with a BFS for each leg is slower and trickier; BFS over (cell, mask) handles it in one search.

Spot it: Shortest moves on a grid → BFS, but the position alone isn't the state: what you can do depends on the keys held. Use state (r, c, mask) where mask has a bit per key (at most 2⁶ = 64 masks).

Why not another pattern? BFS on cells alone forbids revisiting a cell after picking up a key, which is often necessary.

Approach:

1. Find @ and the number of keys; goal = (1 << keys) − 1.
2. BFS from (start, mask 0). Skip walls and locks whose key bit isn't set.
3. Stepping on a key sets its bit. Return the distance when mask == goal.

from collections import deque

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        rows, cols = len(grid), len(grid[0])
        keys = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "@":
                    start = (r, c)
                elif grid[r][c].islower():
                    keys += 1
        goal = (1 << keys) - 1  # every key bit set
        queue = deque([(start[0], start[1], 0, 0)])  # row, col, keys held, moves
        seen = {(start[0], start[1], 0)}
        while queue:
            r, c, mask, moves = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] == "#":
                    continue
                cell = grid[nr][nc]
                if cell.isupper() and not mask >> (ord(cell) - ord("A")) & 1:
                    continue  # locked and we don't have the key
                nmask = mask
                if cell.islower():
                    nmask = mask | 1 << (ord(cell) - ord("a"))  # pick up the key
                if nmask == goal:
                    return moves + 1
                if (nr, nc, nmask) not in seen:
                    seen.add((nr, nc, nmask))
                    queue.append((nr, nc, nmask, moves + 1))
        return -1

What the code is doing, line by line:

1. The state includes the keys held, so revisiting a cell with more keys is allowed and useful.
2. A lock is passable only when its key's bit is set in the mask.
3. BFS reaches every state in the fewest moves, so the first time the mask is complete is optimal.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A lock blocks the only path to its own key → −1.
• Keys collected in a non-obvious order.
• A single key next to the start.

Complexity: O(m · n · 2ᴷ) time and space (K ≤ 6 keys).

Problem: From index i you can move to i − 1, i + 1, or any j with arr[j] == arr[i]. Return the fewest steps from index 0 to the last index.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 5 * 10⁴ · -10⁸ ≤ arr[i] ≤ 10⁸

From brute force to the pattern: Scanning each value group from every index is O(n²) for repeated values. Clearing groups after first use makes BFS O(n).

Spot it: Fewest steps on an unweighted graph → BFS. The catch: equal values form cliques with up to n² edges. Once a value's group has been expanded, every member is already queued, so delete the group to never scan it again.

Why not another pattern? Plain BFS rescanning each value group from every member is O(n²) on arrays like [7,7,7,…].

Approach:

1. Map each value to its list of indices.
2. BFS from 0; neighbours: i − 1, i + 1, and every index in groups[arr[i]].
3. After using groups[arr[i]], clear it.
4. Return the layer when the last index is reached.

from collections import defaultdict, deque

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        groups = defaultdict(list)
        for i, x in enumerate(arr):
            groups[x].append(i)
        seen = [False] * n
        seen[0] = True
        queue = deque([0])
        steps = 0
        while queue:
            for _ in range(len(queue)):
                i = queue.popleft()
                if i == n - 1:
                    return steps
                for j in groups[arr[i]] + [i - 1, i + 1]:
                    if 0 <= j < n and not seen[j]:
                        seen[j] = True
                        queue.append(j)
                groups[arr[i]] = []  # every equal-valued index is queued now: never scan them again
            steps += 1
        return -1

What the code is doing, line by line:

1. The value groups are the teleport edges.
2. Clearing a group after one use is what keeps the BFS linear: each group is scanned once in total.
3. BFS layers count steps, so reaching n − 1 returns the minimum.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 0.
• All values equal → 1 step.
• No repeated values (only ±1 moves).

Complexity: O(n) time and space.

Problem: Every edge takes time minutes; all signals toggle green/red every change minutes and you may leave only on green. Return the second smallest (strictly larger) arrival time from 1 to n.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁴ · n - 1 ≤ edges.length ≤ min(2 * 10⁴, n * (n - 1) / 2) · edges[i].length == 2 · 1 ≤ ui, vi ≤ n · ui != vi · There are no duplicate edges. · Each vertex can be reached directly or indirectly from every other vertex. · 1 ≤ time, change ≤ 10³

From brute force to the pattern: Enumerating paths is exponential; Dijkstra over (node, rank) works but a two-visit BFS is simpler and linear.

Spot it: Signals are shared, so total time depends only on the number of edges walked: fewer edges is always faster. So find the second smallest distinct path length (in edges) with a BFS that lets each node be reached twice (first and second distinct distance), then simulate the signals along that many edges.

Why not another pattern? Dijkstra on times works but is overkill; time is monotone in edge count, so BFS on counts is enough.

Approach:

1. BFS storing first[v] and second[v] (distinct edge counts).
2. When reaching v with distance d: if first is unset, set it; elif d > first[v] and second is unset, set second. Enqueue only on such updates.
3. Simulate second[n] edges: before each edge, if the light is red ((t // change) % 2 == 1), wait until it turns green; then add time.

from collections import deque

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        adj = [[] for _ in range(n + 1)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        first = [-1] * (n + 1)  # shortest edge count to each node
        second = [-1] * (n + 1)  # second shortest (strictly larger)
        first[1] = 0
        queue = deque([(1, 0)])
        while queue:
            u, d = queue.popleft()
            for v in adj[u]:
                if first[v] == -1:
                    first[v] = d + 1
                    queue.append((v, d + 1))
                elif second[v] == -1 and d + 1 > first[v]:
                    second[v] = d + 1  # a strictly longer way in
                    queue.append((v, d + 1))
        t = 0
        for _ in range(second[n]):  # walk that many edges
            if (t // change) % 2 == 1:
                t = (t // change + 1) * change  # red: wait for green
            t += time
        return t

What the code is doing, line by line:

1. Everyone sees the same signal schedule, so a path with more edges never arrives earlier: comparing edge counts is enough.
2. Each node is enqueued at most twice (first and second distance), keeping the BFS linear.
3. The second distinct count always exists: you can bounce back and forth on an edge to add 2.
4. The simulation waits whenever the light is red at departure, then traverses the edge.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Second path is the shortest + 2 (bouncing on an edge).
• Waiting at red lights.
• n = 2 with a single edge.

Complexity: O(n + e) time and space.

Problem: Find a water cell whose distance to the nearest land is maximal (Manhattan), or −1 if there's no land or no water.

Solve it on LeetCode ↗

Constraints: n == grid.length · n == grid[i].length · 1 ≤ n ≤ 100 · grid[i][j] is 0 or 1

From brute force to the pattern: BFS per water cell is O(n⁴); multi-source BFS is O(n²).

Spot it: Distance to the nearest land for every cell → multi-source BFS starting from all land at once; BFS layers are the distances.

Why not another pattern? BFS from each water cell separately is O(n⁴).

Approach:

1. Queue all land cells.
2. BFS layer by layer into water, marking visited.
3. The number of layers processed is the answer (−1 if no water or no land).

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        queue = deque((r, c) for r in range(n) for c in range(n) if grid[r][c] == 1)
        if len(queue) in (0, n * n):
            return -1  # no land, or no water
        dist = -1
        while queue:
            dist += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                        grid[nr][nc] = 1  # reached: mark as visited
                        queue.append((nr, nc))
        return dist

What the code is doing, line by line:

1. All land starts at distance 0, so a water cell is first reached at its distance to the nearest land.
2. In a grid without obstacles, BFS steps equal Manhattan distance.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All land or all water → −1.
• One land cell.
• Land in the middle.

Complexity: O(n²) time and space.

Problem: Using htmlParser.getUrls(url), crawl every page reachable from startUrl on the same hostname (any order).

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ urls.length ≤ 1000 · 1 ≤ urls[i].length ≤ 300 · startUrl is one of the urls · Hostname label must be from 1 to 63 characters long, including the dots, may contain only the ASCII letters from 'a' to 'z', digits from '0' to '9' and the hyphen-minus character ('-') · You may assume there're no duplicates in the URL library

From brute force to the pattern: This is the plain traversal; the visited set is what makes it finite.

Spot it: Pages and links are a graph; visit everything reachable → BFS (or DFS) with a visited set, filtered by hostname.

Why not another pattern? Recursion without a visited set loops forever on cyclic links.

Approach:

1. host = startUrl.split('/')[2].
2. BFS from startUrl; for each link with the same host and not seen, enqueue it.

from collections import deque

class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        host = startUrl.split("/")[2]  # "http://host/path" -> host
        seen = {startUrl}
        queue = deque([startUrl])
        while queue:
            url = queue.popleft()
            for link in htmlParser.getUrls(url):
                if link not in seen and link.split("/")[2] == host:
                    seen.add(link)  # same site, not visited yet
                    queue.append(link)
        return list(seen)

What the code is doing, line by line:

1. Splitting on / gives ['http:', '', host, …].
2. Marking URLs when enqueued avoids duplicates in the queue.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Links to other hosts (skip).
• Cycles of links.
• Pages with no links.

Complexity: O(V + E) time over pages and links, O(V) space.

Problem: Return the videos watched by people at shortest distance exactly level from id, ordered by frequency then name.

Solve it on LeetCode ↗

Constraints: n == watchedVideos.length == friends.length · 2 ≤ n ≤ 100 · 1 ≤ watchedVideos[i].length ≤ 100 · 1 ≤ watchedVideos[i][j].length ≤ 8 · 0 ≤ friends[i].length < n · 0 ≤ friends[i][j] < n · 0 ≤ id < n · 1 ≤ level < n · if friends[i] contains j, then friends[j] contains i

From brute force to the pattern: DFS can reach people through longer paths; BFS layers are exact.

Spot it: "Friends at distance exactly k" → BFS by layers. Then count videos with a hash map and sort.

Why not another pattern? DFS doesn't give shortest distances.

Approach:

1. BFS from id for level layers with a visited set.
2. Count videos of the people in the final layer.
3. Sort by (count, name).

from collections import Counter

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        seen = {id}
        layer = [id]
        for _ in range(level):  # move out one layer at a time
            nxt = []
            for p in layer:
                for f in friends[p]:
                    if f not in seen:
                        seen.add(f)
                        nxt.append(f)
            layer = nxt
        count = Counter(v for p in layer for v in watchedVideos[p])
        return sorted(count, key=lambda v: (count[v], v))  # rarest first, then alphabetical

What the code is doing, line by line:

1. Marking people as seen when first reached keeps only shortest distances.
2. Sorting by (frequency, name) matches the required order.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Level beyond everyone → [].
• Ties in frequency (alphabetical).
• A person reachable at several distances.

Complexity: O(V + E + W log W) time, where W is the number of distinct videos.

Problem: Move up/down/left/right (cost 1) avoiding #; stepping on a letter lets you teleport to any same letter for free, once per letter. Return the fewest moves.

Solve it on LeetCode ↗

Constraints: 1 ≤ m == matrix.length ≤ 10³ · 1 ≤ n == matrix[i].length ≤ 10³ · matrix[i][j] is either '#', '.', or an uppercase English letter. · matrix[0][0] is not an obstacle.

From brute force to the pattern: Tracking used letters in the state is 2²⁶ times bigger; using each letter at its first (cheapest) visit is enough.

Spot it: Edges of weight 0 (teleport) and 1 (move) → 0-1 BFS with a deque. Like Jump Game IV, expand each letter's portal group only the first time that letter is popped (the earliest pop has the smallest distance, so later uses can't help).

Why not another pattern? Plain BFS mishandles zero-cost teleports; tracking which letters were used in the state blows up.

Approach:

1. Group cells by letter.
2. Deque from (0, 0) with distance 0.
3. Pop a cell; if it's an unused letter, set every same-letter cell to this distance (push front).
4. Normal moves cost 1 (push back).

from collections import defaultdict, deque

class Solution:
    def minMoves(self, matrix: List[str]) -> int:
        m, n = len(matrix), len(matrix[0])
        portals = defaultdict(list)
        for r in range(m):
            for c in range(n):
                if matrix[r][c].isupper():
                    portals[matrix[r][c]].append((r, c))
        INF = float("inf")
        dist = [[INF] * n for _ in range(m)]
        dist[0][0] = 0
        dq = deque([(0, 0)])
        used = set()
        while dq:
            r, c = dq.popleft()
            d = dist[r][c]
            if (r, c) == (m - 1, n - 1):
                return d
            ch = matrix[r][c]
            if ch.isupper() and ch not in used:
                used.add(ch)  # this letter's teleport is spent here, at its cheapest
                for pr, pc in portals[ch]:
                    if d < dist[pr][pc]:
                        dist[pr][pc] = d
                        dq.appendleft((pr, pc))  # free move: same distance
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] != "#" and d + 1 < dist[nr][nc]:
                    dist[nr][nc] = d + 1
                    dq.append((nr, nc))
        return -1

What the code is doing, line by line:

1. The deque stays sorted by distance: zero-cost teleports go to the front, moves to the back.
2. The first time a letter is popped is at its smallest distance, so teleporting from there dominates any later use; the once-per-letter rule never hurts.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Start or end on a portal.
• Unreachable end → −1.
• Portals behind walls.

Complexity: O(m · n) time and space.

Problem: Return the fewest swaps of two letters to turn s1 into the anagram s2.

Solve it on LeetCode ↗

Constraints: 1 ≤ s1.length ≤ 20 · s2.length == s1.length · s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}. · s2 is an anagram of s1.

From brute force to the pattern: BFS with all O(n²) swaps explodes; fixing the first mismatch keeps the search small.

Spot it: Fewest swaps → BFS where each state is a string. Branching is cut down by always fixing the first mismatch i: swap it with a later j where cur[j] == s2[i] (and preferably cur[j] != s2[j]).

Why not another pattern? Greedy swapping isn't optimal when cycles of length > 2 exist; trying all swaps is far too many states.

Approach:

1. Queue starts with s1, distance 0.
2. Pop cur; find the first i with cur[i] != s2[i].
3. For each j > i with cur[j] == s2[i] and cur[j] != s2[j]: swap, enqueue if new.
4. Return the distance when cur == s2.

from collections import deque

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        seen = {s1}
        queue = deque([(s1, 0)])
        while queue:
            cur, swaps = queue.popleft()
            if cur == s2:
                return swaps
            i = 0
            while cur[i] == s2[i]:
                i += 1  # first position that's wrong
            for j in range(i + 1, len(cur)):
                if cur[j] == s2[i] and cur[j] != s2[j]:  # brings the right letter to i, and j was wrong anyway
                    nxt = cur[:i] + cur[j] + cur[i + 1:j] + cur[i] + cur[j + 1:]
                    if nxt not in seen:
                        seen.add(nxt)
                        queue.append((nxt, swaps + 1))
        return -1

What the code is doing, line by line:

1. Fixing the first mismatch first doesn't lose optimality: some optimal sequence fixes it with one of these swaps.
2. Skipping j that are already correct avoids pointless moves.
3. BFS returns the fewest swaps.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already equal → 0.
• A 2-cycle (one swap).
• Long cycles of letters.

Complexity: Exponential in the worst case but small for length ≤ 20 with this pruning.

Problem: On an infinite board, return the fewest knight moves from (0, 0) to (x, y).

Solve it on LeetCode ↗ (Premium)

Constraints: -300 ≤ x, y ≤ 300 · 0 ≤ |x| + |y| ≤ 300

From brute force to the pattern: Unbounded BFS in all quadrants works but explores 4× more; symmetry trims it.

Spot it: Fewest moves on an unweighted graph → BFS. By symmetry, target (|x|, |y|) and stay in the first quadrant, allowing coordinates down to −2 (some shortest paths dip slightly below the axes).

Why not another pattern? DFS doesn't find shortest paths; an unbounded BFS explores four quadrants for nothing.

Approach:

1. x, y = |x|, |y|.
2. BFS from (0, 0) with the 8 knight moves, skipping cells with a coordinate below −2.
3. Return the distance when the target is reached.

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        x, y = abs(x), abs(y)  # all four quadrants look the same
        moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
        seen = {(0, 0)}
        queue = deque([(0, 0, 0)])
        while queue:
            r, c, d = queue.popleft()
            if (r, c) == (x, y):
                return d
            for dr, dc in moves:
                nr, nc = r + dr, c + dc
                if nr >= -2 and nc >= -2 and (nr, nc) not in seen:  # small dip below the axes is enough
                    seen.add((nr, nc))
                    queue.append((nr, nc, d + 1))
        return -1

What the code is doing, line by line:

1. Reflecting the target into the first quadrant doesn't change the answer.
2. Paths to targets near the origin (like (1, 1)) need to step to negative coordinates, but never below −2.
3. BFS returns the shortest distance.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Target (0, 0) → 0.
• (1, 1) → 2.
• Far targets.

Complexity: O(|x| · |y|) time and space.