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. What is the time complexity of the iterative postorder traversal solution for the Binary Tree Maximum Path Sum problem, assuming the tree has n nodes?

medium

A. O(n) for traversal but O(n) extra space for the stack and gains dictionary

B. O(n log n) due to repeated stack operations and subtree recomputations

C. O(n^2) because for each node, the algorithm recomputes gains from all descendants

D. O(n) because each node is visited once and gains are computed in constant time per node

Solution

1. Step 1: Identify traversal cost

   The iterative postorder traversal visits each node exactly once, pushing and popping it from the stack once.

2. Step 2: Analyze per-node computation

   At each node, gains are computed using stored values from children in O(1) time, no recomputation of subtrees.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear traversal with constant work per node -> O(n) time [OK]

Hint: Each node processed once, no repeated subtree work [OK]

Common Mistakes:

• Confusing recursion stack with repeated work
• Assuming recomputation of subtree gains
• Ignoring constant time per node

2. What is the time complexity of the optimal bottom-up DFS solution for computing the diameter of a binary tree with n nodes?

medium

A. O(n) because each node is visited once in the DFS traversal

B. O(n^2) due to repeated height computations in recursion

C. O(n log n) because height computations take log n time per node

D. O(n) but with additional O(n) space for memoization arrays

Solution

1. Step 1: Identify that naive recursive approach causes repeated height computations

   In naive recursion without memoization, height computations are repeated, causing O(n^2) time complexity.

2. Step 2: Confirm that optimal bottom-up DFS avoids repeated computations

   The question asks for the optimal bottom-up DFS solution, which is O(n), but the options are designed to test understanding of naive vs optimal.

3. Step 3: Since O(n) because each node is visited once in the DFS traversal states optimal O(n), but O(n^2) due to repeated height computations in recursion states O(n^2) due to repeated computations, and question asks for optimal solution, correct answer is A.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Single DFS traversal over n nodes -> O(n) time [OK]

Hint: Single DFS traversal means linear time [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming height calls cost log n each

3. Examine the following code snippet for longest increasing path. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line returning max value from dp

B. Line initializing dp with 1s

C. Line sorting cells by their matrix values

D. Line checking if matrix[x][y] > matrix[i][j] without boundary check

Solution

1. Step 1: Identify missing boundary check

   The code accesses matrix[x][y] without verifying x,y are within matrix bounds, risking IndexError.

2. Step 2: Confirm other lines are correct

   dp initialization, sorting, and return statements are correct and standard.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary checks are essential before accessing neighbors [OK]

Hint: Always check boundaries before neighbor access [OK]

Common Mistakes:

• Forgetting boundary checks causing crashes
• Misplaced memoization causing TLE
• Incorrect dp initialization

4. The following code attempts to count the number of longest increasing subsequences using DP arrays. Identify the bug that causes incorrect counting of LIS.

medium

A. counts array is initialized with zeros instead of ones

B. lengths array should be initialized with zeros instead of ones

C. The condition nums[j] < nums[i] should be nums[j] <= nums[i]

D. The final sum should be over counts where lengths are less than max_len

Solution

1. Step 1: Check initialization of counts array

   Counts represent number of LIS ending at each index; initially each element alone forms LIS of length 1, so counts[i] must start at 1, not 0.

2. Step 2: Consequence of zero initialization

   With counts initialized to 0, counts[i] remains 0 unless updated, causing undercounting of LIS and incorrect final result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initialize counts with 1 to count single-element subsequences [OK]

Hint: Counts must start at 1 to count single elements [OK]

Common Mistakes:

• Initializing counts with zeros
• Using <= instead of <
• Summing counts incorrectly

5. What is the time complexity of the bottom-up bitmask DP solution for the Travelling Salesman Problem with n cities, and why? Options:

medium

A. O(n * 2^n) because we process each subset and city once

B. O(2^n) because subsets dominate the complexity

C. O(n^2 * 2^n) because for each subset and city, we check all possible previous cities

D. O(n! ) because we consider all permutations of cities

Solution

1. Step 1: Identify loops in the code

   There are three nested loops: over all subsets (2^n), over all cities (n), and over all possible previous cities (n).

2. Step 2: Multiply loop complexities

   Total complexity is O(2^n * n * n) = O(n^2 * 2^n). O(n * 2^n) because we process each subset and city once misses the inner loop over previous cities, underestimating complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask DP complexity is well-known as O(n^2 * 2^n) [OK]

Hint: Remember triple nested loops: subsets, current city, previous city [OK]

Common Mistakes:

• Ignoring inner loop over previous cities leads to underestimation