Shortest Path Visiting All Nodes

▶

Steps

setup

Initialize variables and constants

We determine the number of nodes n=4 and compute all_visited mask = 1111 binary (decimal 15), representing all nodes visited.

💡 Knowing the total number of nodes and the bitmask representing all visited nodes sets the foundation for state compression.

Line:

n = len(graph)
all_visited = (1 << n) - 1

💡 The bitmask all_visited will be used to check when all nodes have been visited.

setup

Initialize BFS queues and visited dictionaries

We initialize two queues q1 and q2 and two visited dictionaries visited1 and visited2. For each node i, we enqueue (i, mask) in q1 and (i, all_visited ^ mask) in q2, marking them visited with distance 0.

💡 Starting BFS from all single nodes simultaneously and from the complement masks in the backward search sets up the bidirectional search.

Line:

for i in range(n):
    mask = 1 << i
    q1.append((i, mask))
    visited1[(i, mask)] = 0
    q2.append((i, all_visited ^ mask))
    visited2[(i, all_visited ^ mask)] = 0

💡 This step encodes the initial states for both BFS directions, enabling simultaneous exploration.

traverse

Start expanding from forward queue q1: pop (0, 0001)

We pop the first state (node=0, visited_mask=0001) from q1 to expand its neighbors.

💡 Expanding one state at a time shows how BFS explores new states by visiting neighbors and updating visited masks.

Line:

node, mask = q1.popleft()
dist = visited1[(node, mask)]

💡 This step shows the BFS frontier moving forward from node 0 with only node 0 visited.

expand

Expand neighbors of (0, 0001) in q1

We explore neighbors of node 0: nodes 1, 2, and 3. For each, we compute next_mask by adding the neighbor to visited_mask and enqueue new states if unseen.

💡 This step shows how visiting neighbors updates the visited mask and expands BFS states.

Line:

for nei in graph[node]:
    next_mask = mask | (1 << nei)
    if (nei, next_mask) not in visited1:
        visited1[(nei, next_mask)] = dist + 1
        q1.append((nei, next_mask))

💡 Adding neighbors to the visited mask creates new states representing paths that have visited more nodes.

traverse

Start expanding from backward queue q2: pop (0, 1110)

We pop the first state (node=0, visited_mask=1110) from q2 to expand neighbors backward.

💡 Backward BFS explores states representing nodes not yet visited, complementing forward BFS.

Line:

node, mask = q2.popleft()
dist = visited2[(node, mask)]

💡 Backward BFS starts from states where all nodes except one are visited.

expand

Expand neighbors of (0, 1110) in q2

We explore neighbors of node 0: nodes 1, 2, and 3. For each, we compute next_mask by removing the neighbor from visited_mask and enqueue new states if unseen.

💡 Backward BFS removes nodes from the visited mask to represent states with fewer nodes visited.

Line:

for nei in graph[node]:
    next_mask = mask & ~(1 << nei)
    if (nei, next_mask) not in visited2:
        visited2[(nei, next_mask)] = dist + 1
        q2.append((nei, next_mask))

💡 Backward BFS explores states with fewer nodes visited by removing neighbors from the mask.

traverse

Expand from forward queue q1: pop (1, 0010)

We pop (node=1, mask=0010) from q1 to explore neighbors and update states.

💡 Continuing forward BFS expansion explores new states from node 1 with node 1 visited.

Line:

node, mask = q1.popleft()
dist = visited1[(node, mask)]

💡 This step shows BFS progressing from node 1 with visited mask 0010.

expand

Expand neighbors of (1, 0010) in q1

Node 1 has neighbor 0. We add node 0 to visited mask: next_mask = 0011. Since (0, 0011) is new, enqueue it.

💡 Expanding neighbors updates visited masks and grows BFS states.

Line:

for nei in graph[node]:
    next_mask = mask | (1 << nei)
    if (nei, next_mask) not in visited1:
        visited1[(nei, next_mask)] = dist + 1
        q1.append((nei, next_mask))

💡 Visiting neighbors can revisit nodes but with a larger visited set.

traverse

Expand from backward queue q2: pop (1, 1101)

We pop (node=1, mask=1101) from q2 to explore neighbors backward.

💡 Backward BFS continues exploring states with nodes not yet visited.

Line:

node, mask = q2.popleft()
dist = visited2[(node, mask)]

💡 Backward BFS explores states with some nodes still unvisited.

expand

Expand neighbors of (1, 1101) in q2

Node 1 has neighbor 0. We remove node 0 from mask: next_mask = 1100. Since (0, 1100) is new, enqueue it.

💡 Backward BFS removes nodes from visited mask to explore states with fewer visited nodes.

Line:

for nei in graph[node]:
    next_mask = mask & ~(1 << nei)
    if (nei, next_mask) not in visited2:
        visited2[(nei, next_mask)] = dist + 1
        q2.append((nei, next_mask))

💡 Backward BFS explores states closer to the empty visited set by removing nodes.

compare

Forward BFS finds meeting state (0, 0011) in backward visited2

When expanding forward BFS, we find state (0, 0011) is also in backward visited2 with distance 2. The total distance is 2 + 2 = 4.

💡 Finding a state in both visited sets means the two BFS meet, giving the shortest path length.

Line:

if (node, mask) in visited2:
    return dist + visited2[(node, mask)]

💡 The shortest path visiting all nodes is found when forward and backward BFS meet at the same state.

from collections import deque
from typing import List

def shortestPathLength(graph: List[List[int]]) -> int:
    n = len(graph)  # STEP 1
    all_visited = (1 << n) - 1  # STEP 1

    q1 = deque()  # STEP 2
    q2 = deque()  # STEP 2

    visited1 = dict()  # STEP 2
    visited2 = dict()  # STEP 2

    for i in range(n):  # STEP 2
        mask = 1 << i
        q1.append((i, mask))
        visited1[(i, mask)] = 0
        q2.append((i, all_visited ^ mask))
        visited2[(i, all_visited ^ mask)] = 0

    while q1 and q2:
        for _ in range(len(q1)):  # STEP 3-4
            node, mask = q1.popleft()
            dist = visited1[(node, mask)]
            if (node, mask) in visited2:  # STEP 11
                return dist + visited2[(node, mask)]
            for nei in graph[node]:
                next_mask = mask | (1 << nei)
                if (nei, next_mask) not in visited1:
                    visited1[(nei, next_mask)] = dist + 1
                    q1.append((nei, next_mask))

        for _ in range(len(q2)):  # STEP 5-6,9-10
            node, mask = q2.popleft()
            dist = visited2[(node, mask)]
            if (node, mask) in visited1:
                return dist + visited1[(node, mask)]
            for nei in graph[node]:
                next_mask = mask & ~(1 << nei)
                if (nei, next_mask) not in visited2:
                    visited2[(nei, next_mask)] = dist + 1
                    q2.append((nei, next_mask))
    return -1

📊

Shortest Path Visiting All Nodes - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how states are represented by (node, visited_mask) pairs and how the two BFS fronts progress and meet, which is difficult to grasp from code alone.

Visiting: none

0

1

2

3

Visiting: none

0

1

2

3

Queue / Stack

0, mask=00011, mask=00102, mask=01003, mask=1000

Visiting: 0

0

1

2

3

Queue / Stack

1, mask=00102, mask=01003, mask=1000

Visiting: 0

0

1

2

3

Queue / Stack

1, mask=00102, mask=01003, mask=10001, mask=00112, mask=01013, mask=1001

Visiting: 0

0

1

2

3

Queue / Stack

1, mask=11012, mask=10113, mask=0111

Visiting: 0

0

1

2

3

Queue / Stack

1, mask=11012, mask=10113, mask=01111, mask=11002, mask=10103, mask=0110

Visiting: 1

0

1

2

3

Queue / Stack

2, mask=01003, mask=10001, mask=00112, mask=01013, mask=1001

Visiting: 1

0

1

2

3

Queue / Stack

2, mask=01003, mask=10001, mask=00112, mask=01013, mask=10010, mask=0011

Visiting: 1

0

1

2

3

Queue / Stack

2, mask=10113, mask=01111, mask=11002, mask=10103, mask=0110

Visiting: 1

0

1

2

3

Queue / Stack

2, mask=10113, mask=01111, mask=11002, mask=10103, mask=01100, mask=1100

Visiting: 0

0

1

2

3

Queue / Stack

2, mask=01003, mask=10002, mask=01013, mask=10010, mask=0011

Key Takeaways

✓ Bidirectional BFS with state compression efficiently finds the shortest path visiting all nodes by meeting in the middle.

This insight is hard to see from code alone because it requires understanding how two BFS frontiers with complex states interact.

✓ States are represented as (node, visited_mask) pairs, encoding both current position and visited nodes compactly.

Visualizing these states clarifies how the algorithm tracks progress through the graph and avoids redundant work.

✓ The algorithm alternates expanding forward and backward BFS queues, checking for overlap to detect when the shortest path is found.

Seeing this alternating expansion and overlap detection step-by-step reveals the core mechanism of bidirectional search.

Practice

1. You are given k sorted lists of integers. Your task is to find the smallest range that includes at least one number from each of the k lists. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach that always picks the smallest current element and expands the range until all lists are covered.

B. Merge all lists into one sorted array with list indices, then use a two-pointer sliding window to find the minimal range covering all lists.

C. Apply dynamic programming to track the minimal range for subsets of lists incrementally.

D. Enumerate all possible combinations of elements from each list and select the combination with the smallest range.

Solution

1. Step 1: Understand problem constraints

   The problem requires a range covering at least one element from each list, which suggests tracking coverage across lists.

2. Step 2: Evaluate approaches

   Greedy alone fails because it doesn't guarantee minimal range; DP is not suitable due to combinatorial explosion; brute force enumerates all combos but is inefficient. Merging all lists and using two pointers efficiently tracks coverage and minimal range.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer on merged array is known optimal [OK]

Hint: Two pointers on merged array track coverage efficiently [OK]

Common Mistakes:

• Thinking greedy alone suffices
• Assuming DP applies directly
• Using brute force for large inputs

2. You are given an array representing the elevation map where the width of each bar is 1. You need to find how much water can be trapped after raining. Which approach guarantees an optimal solution with linear time and constant space complexity?

easy

A. Use nested loops to find the maximum height to the left and right of each bar and calculate trapped water accordingly.

B. Use two pointers starting from both ends, moving inward, updating left_max and right_max, and accumulating trapped water based on comparisons.

C. Use dynamic programming with a 2D table storing water trapped between every pair of bars.

D. Use a greedy approach that always traps water at the current lowest bar without considering future bars.

Solution

1. Step 1: Understand problem constraints

   The problem requires calculating trapped water efficiently with minimal space.

2. Step 2: Evaluate approaches

   Nested loops (brute force) are O(n²), DP with 2D table is inefficient, greedy fails on complex cases. The two-pointer approach uses O(n) time and O(1) space by moving pointers inward and updating max heights.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer approach is known optimal for trapping rain water [OK]

Hint: Two pointers with max updates -> optimal O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing greedy with two-pointer approach
• Assuming DP with 2D table is needed
• Believing brute force is acceptable for large inputs

3. What is the time complexity of the optimal Alien Dictionary solution using Kahn's algorithm with early cycle detection and edge deduplication, given C as the total number of characters in all words and U as the number of unique characters?

medium

A. O(C log U) due to sorting characters during graph construction

B. O(U^2) due to checking all pairs of characters

C. O(C * U) because each character is compared with all unique characters

D. O(C + U + E) where E is number of edges, since graph construction and BFS visit all characters and edges once

Solution

1. Step 1: Analyze graph construction cost

   Each adjacent word pair is compared up to min length, total comparisons proportional to total characters C.

2. Step 2: Analyze topological sort cost

   BFS visits each node (U) and each edge (E) once; E ≤ C since edges come from character comparisons.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity O(C + U + E) matches linear graph traversal [OK]

Hint: Graph traversal cost dominates, not pairwise character comparisons [OK]

Common Mistakes:

• Assuming quadratic due to character pairs
• Confusing edges with nodes
• Forgetting BFS linearity

4. The following code attempts to solve the Russian Doll Envelopes problem optimally. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes with key (x[0], x[1]) ascending both

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing tails element at found index

Solution

1. Step 1: Examine sorting key

   Sorting by (width asc, height asc) allows envelopes with same width and increasing height, which breaks strict nesting rules.

2. Step 2: Correct sorting key

   Sorting by (width asc, height desc) prevents envelopes with equal width but increasing height from being counted incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing sorting to (x[0], -x[1]) fixes the bug [OK]

Hint: Sort height descending for equal widths to avoid counting duplicates [OK]

Common Mistakes:

• Sorting both width and height ascending
• Using <= instead of < in comparisons
• Not handling equal widths properly

5. Suppose you want to find the median of two sorted arrays where elements can be repeated infinitely (i.e., arrays represent multisets with unlimited duplicates). Which modification to the optimal binary search partition approach is necessary to handle this scenario correctly?

hard

A. Modify the partition condition to handle infinite duplicates by counting occurrences explicitly.

B. No modification needed; the existing binary search partition approach works as is.

C. Switch to a two-pointer partial merge approach to handle duplicates efficiently.

D. Use a frequency map and binary search on value range instead of indices.

Solution

1. Step 1: Understand infinite duplicates impact

   Infinite duplicates mean the arrays represent multisets with repeated elements beyond fixed length, so index-based partitioning is insufficient.

2. Step 2: Modify partition condition

   The binary search partition must be adapted to count occurrences and handle duplicates explicitly to find correct median position.

3. Step 3: Why other options fail

   No modification ignores duplicates; two-pointer merge loses logarithmic efficiency; frequency map changes problem nature.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Handling infinite duplicates requires counting occurrences in partition [OK]

Hint: Infinite duplicates require counting occurrences in partition [OK]

Common Mistakes:

• Assuming no change needed for duplicates
• Switching to merge loses optimal time
• Using frequency map changes problem scope