Shortest Path Visiting All Nodes

📋

Problem

Imagine a delivery robot that must visit every house in a neighborhood exactly once in the shortest possible route. How can it find this route efficiently?

Given an undirected, connected graph with n nodes labeled from 0 to n-1, find the length of the shortest path that visits every node at least once. You can start and stop at any node, and you may revisit nodes multiple times.

1 ≤ n ≤ 12graph.length == n0 ≤ graph[i].length < ngraph[i] does not contain iAll edges are bidirectionalThe graph is connected

Edge cases: Single node graph → shortest path length is 0Graph with nodes connected in a line → path length equals n-1Complete graph → shortest path length is n-1

</>

IDE

def shortestPathLength(graph: List[List[int]]) -> int:public int shortestPathLength(int[][] graph)int shortestPathLength(vector<vector<int>>& graph)function shortestPathLength(graph)

def shortestPathLength(graph: List[List[int]]) -> int:
    # Write your solution here
    pass

class Solution {
    public int shortestPathLength(int[][] graph) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int shortestPathLength(vector<vector<int>>& graph) {
    // Write your solution here
    return 0;
}

function shortestPathLength(graph) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to missing BFS or bitmask logic.✅ Initialize BFS queue with all nodes and their bitmask states; do not return 0 unless graph has single node.

Wrong: n-1 for all graphsAssuming shortest path length is always n-1 ignoring revisits and graph structure.✅ Implement BFS with bitmask to explore all states and find minimal path length.

Wrong: Longer than expected path lengthUsing greedy approach picking nearest unvisited node only.✅ Use BFS with bitmask to explore all possible paths and states.

Wrong: TLE or timeoutUsing brute force DFS without memoization or BFS with bitmask.✅ Implement BFS with bitmask DP or bidirectional BFS to reduce complexity.

Wrong: Off-by-one errors in path lengthIncorrect bitmask initialization or distance increments.✅ Ensure visited bitmask includes starting node and increment distance by 1 per edge traversal.

✓

Test Cases

Focus on handling smallest and simplest graphs correctly before tackling edges.

Understand why greedy or naive DFS approaches fail on graphs with cycles and revisits.

Optimize your solution to BFS with bitmask DP to handle the largest inputs efficiently.

t1_01basic

Input[[1,2,3],[0],[0],[0]]

Expected4

⏱ Performance - must finish in 2000ms

Start at node 1, path: 1 -> 0 -> 2 -> 0 -> 3 visits all nodes in 4 steps.

💡 Think about BFS with state to track visited nodes.

💡 Use bitmask to represent visited nodes and BFS queue to explore states.

💡 Initialize BFS from all nodes with their bitmask and find shortest path covering all nodes.

Why it failed: Incorrect output means BFS with state or bitmask is not implemented correctly; fix by ensuring all nodes start in the queue with their own bitmask and track visited states properly.

✓ Correctly computes shortest path length using BFS with bitmask state.

t1_02basic

Input[[1],[0,2,4],[1,3,4],[2],[1,2]]

Expected4

⏱ Performance - must finish in 2000ms

Graph with 5 nodes and edges forming a small network; shortest path length to visit all nodes is 4.

💡 Consider BFS from all nodes simultaneously with bitmask states.

💡 Track visited states carefully to avoid revisiting same state multiple times.

💡 Use a queue of (node, visited_bitmask) and update distances accordingly.

Why it failed: Output too large or too small indicates incorrect state transitions or missing initial states; fix by initializing BFS queue with all nodes and their bitmask and updating visited states correctly.

✓ Correctly finds shortest path length covering all nodes in a connected graph.

t2_01edge

Input[[]]

Expected0

⏱ Performance - must finish in 2000ms

Single node graph with no edges; shortest path length is 0 since node is already visited.

💡 Check behavior when graph has only one node.

💡 The shortest path length should be zero as no moves are needed.

💡 Return 0 immediately if n == 1 or all nodes are trivially visited.

Why it failed: Returning non-zero means code does not handle single node base case; fix by returning 0 if graph length is 1.

✓ Correctly handles single node graph with zero path length.

t2_02edge

Input[[1],[0,2],[1,3],[2]]

Expected3

⏱ Performance - must finish in 2000ms

Nodes connected in a line: shortest path length equals n-1 = 3.

💡 Consider linear chain graph and shortest path visiting all nodes.

💡 Shortest path length should be n-1 for a line graph.

💡 Verify BFS explores neighbors in order and updates visited states correctly.

Why it failed: Output not equal to n-1 means BFS or bitmask logic fails on linear graphs; fix by ensuring all states are explored and distances updated properly.

✓ Correctly computes shortest path length for linear chain graph.

t2_03edge

Input[[1,2,3],[0,2,3],[0,1,3],[0,1,2]]

Expected3

⏱ Performance - must finish in 2000ms

Complete graph with 4 nodes; shortest path length is n-1 = 3.

💡 In a complete graph, shortest path length equals n-1.

💡 Check that BFS does not overcount steps by revisiting nodes unnecessarily.

💡 Ensure bitmask states are updated correctly to avoid redundant paths.

Why it failed: Output greater than n-1 means BFS or state tracking is inefficient or incorrect; fix by pruning visited states and updating distances properly.

✓ Correctly computes shortest path length for complete graph.

t3_01corner

Input[[1],[0,2],[1,3],[2,4],[3]]

Expected4

⏱ Performance - must finish in 2000ms

Graph with cycles; shortest path may revisit nodes but minimal steps is 4.

💡 Beware of greedy approaches that pick nearest unvisited node only.

💡 Use BFS with bitmask to explore all states rather than greedy.

💡 Implement full state tracking to avoid missing shorter paths involving revisits.

Why it failed: Greedy approach fails here by returning longer path; fix by using BFS with bitmask to explore all states.

✓ Correctly handles graphs with cycles using BFS with bitmask.

t3_02corner

Input[[1,2],[0,3],[0,3],[1,2]]

Expected3

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 vs unbounded visits; shortest path length is 3.

💡 Remember nodes can be revisited multiple times; not a 0/1 visit problem.

💡 Track visited nodes with bitmask but allow revisits to minimize path length.

💡 Use BFS with state compression, not simple DFS or greedy.

Why it failed: Confusing 0/1 visit with unbounded causes incorrect longer path; fix by allowing revisits and tracking visited bitmask properly.

✓ Correctly handles multiple revisits with bitmask BFS.

t3_03corner

Input[[1],[0,2],[1,3],[2,4],[3,5],[4]]

Expected5

⏱ Performance - must finish in 2000ms

Off-by-one error test: linear chain of 6 nodes; shortest path length is 5.

💡 Check indexing and bitmask updates carefully to avoid off-by-one errors.

💡 Ensure initial states and visited masks are set correctly for all nodes.

💡 Verify BFS distance increments by 1 per edge traversal.

Why it failed: Off-by-one error causes output to be 4 or 6 instead of 5; fix by correctly initializing visited bitmask and incrementing distance per step.

✓ Correctly computes shortest path length with no off-by-one errors.

t4_01performance

Input[[1,2],[0,3],[0,3],[1,2,4],[3,5],[4,6],[5,7],[6,8],[7,9],[8,10],[9,11],[10]]

Expectednull

⏱ Performance - must finish in 2000ms

n=12, graph is a chain with some extra edges; BFS with bitmask O(n*2^n) must complete within 2s.

💡 This test checks algorithmic efficiency at upper constraint.

💡 Brute force exponential solutions will time out here.

💡 Use BFS with bitmask DP or bidirectional BFS to pass.

Why it failed: TLE indicates exponential brute force or inefficient state pruning; fix by implementing BFS with bitmask DP or bidirectional BFS.

✓ Algorithm runs within time limit confirming O(n*2^n) or better complexity.

Practice

1. Given the following code for the House Robber III problem, what is the final returned value when called with the tree below? Tree structure: ``` 3 / \ 2 3 \ \ 3 1 ```

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[0] + right[0]
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob(root))

easy

A. 6

B. 9

C. 8

D. 7

Solution

1. Step 1: Trace dfs on leaf nodes

   Leaf nodes 3 and 1 return (0,3) and (0,1) respectively.

2. Step 2: Compute dfs for internal nodes

   Node 2: rob_node = 2 + 0 + 0 = 2, not_rob_node = max(0,3) + 0 = 3; returns (3,2). Node 3 (right child): rob_node = 3 + 0 + 0 = 3, not_rob_node = 0 + max(0,1) = 1; returns (1,3). Root 3: rob_node = 3 + 3 + 1 = 7, not_rob_node = max(3,2) + max(1,3) = 3 + 3 = 6.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Maximum is max(6,7) = 7 [OK]

Hint: Trace bottom-up dp states carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Confusing rob and not_rob states at nodes

2. What is the time complexity of the space optimized bitmask DP solution for counting ways to assign unique caps to n people, where caps range up to 100 and each person has a list of caps they can wear?

medium

A. O(n * 2^n)

B. O(100 * 2^n * n)

C. O(2^n * n^2)

D. O(n * 100^n)

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop iterates over caps (up to 100), the middle loop iterates over all masks (2^n), and the inner loop iterates over persons (up to n) who can wear the current cap.

2. Step 2: Combine loop complexities

   Multiplying these gives O(100 * 2^n * n). Other options either omit the cap factor or incorrectly exponentiate caps.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Counting all masks and caps with person checks matches O(100 * 2^n * n) [OK]

Hint: Count loops: caps * masks * persons per cap [OK]

Common Mistakes:

• Ignoring caps loop
• Confusing n with cap count
• Forgetting inner loop over persons

3. Consider the following buggy code for the House Robber III problem. Which line contains the subtle bug that causes incorrect results on some inputs?

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[1] + right[1]  # Bug here
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

medium

A. Line returning max of dfs(root) instead of sum

B. Line computing rob_node sums children rob values instead of not_rob values

C. Line returning (not_rob_node, rob_node) tuple instead of single value

D. Line checking if node is null and returning (0,0)

Solution

1. Step 1: Understand rob_node calculation

   When robbing current node, children cannot be robbed, so we must add left[0] and right[0] (not_rob values).

2. Step 2: Identify bug

   The code incorrectly adds left[1] and right[1] (rob values), causing double counting and invalid solutions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct rob_node uses not_rob children sums [OK]

Hint: Robbing node requires adding children's not_rob values [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple

4. 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

5. The following code attempts to solve the Travelling Salesman Problem using bottom-up bitmask DP. Identify the bug that causes incorrect results on some inputs.

def tsp_bottom_up_buggy(dist):
    n = len(dist)
    ALL_VISITED = (1 << n) - 1
    dp = [[float('inf')] * n for _ in range(1 << n)]
    # BUG: dp[1][0] not initialized

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                for j in range(n):
                    if mask & (1 << j) and i != j:
                        prev_mask = mask ^ (1 << i)
                        dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])

    ans = float('inf')
    for i in range(1, n):
        ans = min(ans, dp[ALL_VISITED][i] + dist[i][0])
    return ans

medium

A. Missing base case initialization dp[1][0] = 0

B. Incorrect calculation of prev_mask = mask ^ (1 << i)

C. Line initializing dp array with float('inf')

D. Final loop over i in range(1, n) missing city 0

Solution

1. Step 1: Check base case initialization

   The DP table must have dp[1][0] = 0 to represent starting at city 0 with only city 0 visited.

2. Step 2: Consequence of missing base case

   Without this, all dp states remain infinite, so no valid path cost is computed, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Base case initialization is essential for DP correctness [OK]

Hint: Always initialize base case dp for starting city [OK]

Common Mistakes:

• Forgetting dp[1][0] initialization leads to infinite costs