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 a binary tree where each node contains an integer value, you need to find the maximum sum of values along any path. The path can start and end at any node, and must be continuous (parent-child connections). Which approach guarantees finding the optimal maximum path sum efficiently?

easy

A. Use a recursive postorder traversal that computes maximum gains from children and updates a global max path sum including both children at each node.

B. Use a greedy traversal that picks the maximum child sum at each node without backtracking.

C. Use a breadth-first search to accumulate sums level by level and pick the maximum sum found.

D. Use dynamic programming on node values treating the tree as a linear array and summing consecutive nodes.

Solution

1. Step 1: Understand the problem requires paths that can bend at any node, including both children.

   A greedy approach that only picks one child at each node misses paths that include both children and the node itself.

2. Step 2: Recognize that a recursive postorder traversal can compute max gains from left and right subtrees, and update a global max including both children plus current node.

   This approach ensures all possible paths are considered and the global max is updated correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy and BFS approaches fail to consider paths bending at nodes [OK]

Hint: Optimal solution uses recursion with global max tracking [OK]

Common Mistakes:

• Greedy picking max child only
• Treating tree as linear array
• Using BFS for path sums

2. You are given an array nums and multiple queries, each query containing two integers x and m. For each query, you want to find the maximum XOR of x with any element in nums that is less than or equal to m. Which algorithmic approach guarantees an optimal solution for large inputs?

easy

A. Greedy approach selecting the largest element less than or equal to m for XOR

B. Brute force nested loops checking all pairs for each query

C. Dynamic programming with memoization over all possible XOR values

D. Sorting nums and queries, then using a bitwise trie with offline queries and two pointers

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; greedy fails because max element ≤ m does not guarantee max XOR.

2. Step 2: Identify optimal approach

   Sorting and offline queries allow incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting + trie + offline queries is known optimal [OK]

Hint: Offline queries + trie + sorting -> optimal [OK]

Common Mistakes:

• Assuming greedy max element ≤ m yields max XOR
• Trying DP over XOR values
• Using brute force for large inputs

3. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n (number of balloons)?

medium

A. O(n * 2^n)

B. O(n^2)

C. O(n^3)

D. O(n^4)

Solution

1. Step 1: Identify nested loops in the bottom-up DP

   There are three nested loops: length (up to n), left (up to n), and i (between left and right), each up to n.

2. Step 2: Calculate total operations

   Multiplying the three loops gives O(n^3) time complexity. The dp table is size n^2, so space is O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Three nested loops over n -> O(n^3) [OK]

Hint: Three nested loops over n cause cubic time [OK]

Common Mistakes:

• Confusing with exponential brute force
• Forgetting the third loop
• Assuming quadratic time

4. The following code snippet is a near-correct implementation of the Trie-based palindrome pairs solution. Which line contains a subtle bug that causes incorrect results on inputs containing empty strings?

medium

A. Line missing palindrome_suffixes append after setting node.index

B. Line checking is_palindrome(word[:len(word)-i]) inside add_word loop

C. Line checking is_palindrome(word[i:]) inside search loop

D. Line returning res when ch not in node.children

Solution

1. Step 1: Identify missing palindrome suffix append

   After setting node.index, the code must append index to palindrome_suffixes to handle empty string cases correctly.

2. Step 2: Understand impact on empty string pairs

   Without this append, pairs involving empty strings and palindromic words are missed, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding palindrome_suffixes append fixes empty string pairing [OK]

Hint: Empty string pairs require palindrome_suffixes append at word end [OK]

Common Mistakes:

• Forgetting to append palindrome_suffixes at word end
• Misplacing palindrome checks
• Incorrect early returns in search

5. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output by adding redundant points or missing height changes?

medium

A. Line where maxH is computed with max(h1, h2)

B. Line where merged appends [x, maxH] without checking last height

C. Line where i and j are incremented in the else block

D. Line where h1 and h2 are initialized to 0 at the start

Solution

1. Step 1: Identify the bug

   The code appends every point without checking if the height changed, causing redundant points.

2. Step 2: Correct approach

   Appending should happen only if merged is empty or last height differs from maxH to avoid duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending unconditionally causes redundant points [OK]

Hint: Check if last height differs before appending new point [OK]

Common Mistakes:

• Appending points even if height unchanged
• Incorrectly incrementing indices causing skips
• Not initializing heights properly