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. Consider the following Python code implementing the optimal DP solution for the stock problem with k transactions. What is the final output when calling maxProfit(1, [1, 5, 2])?

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]
    curr_dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        for t in range(1, k + 1):
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])
        next_dp, curr_dp = curr_dp, next_dp
    return next_dp[k][0]

print(maxProfit(1, [1, 5, 2]))

easy

A. 4

B. 5

C. 3

D. 1

Solution

1. Step 1: Trace dp for i=2 (price=2), t=1

   Initialize next_dp and curr_dp with zeros. At i=2, curr_dp[1][0] = max(-2 + next_dp[1][1], next_dp[1][0]) = max(-2 + 0, 0) = 0; curr_dp[1][1] = max(2 + next_dp[0][0], next_dp[1][1]) = max(2 + 0, 0) = 2.

2. Step 2: Trace dp for i=1 (price=5), t=1

   curr_dp[1][0] = max(-5 + next_dp[1][1], next_dp[1][0]) = max(-5 + 2, 0) = 0; curr_dp[1][1] = max(5 + next_dp[0][0], next_dp[1][1]) = max(5 + 0, 2) = 5.

3. Step 3: Trace dp for i=0 (price=1), t=1

   curr_dp[1][0] = max(-1 + next_dp[1][1], next_dp[1][0]) = max(-1 + 5, 0) = 4; curr_dp[1][1] = max(1 + next_dp[0][0], next_dp[1][1]) = max(1 + 0, 5) = 5.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Maximum profit with 1 transaction is buying at 1 and selling at 5 -> profit 4 [OK]

Hint: Trace dp arrays backward to find max profit [OK]

Common Mistakes:

• Confusing holding and not holding states
• Off-by-one errors in indexing transactions
• Misreading the final dp state to return

2. Consider the following code snippet for computing the maximum path sum in a binary tree. Given the tree with root value 1, left child 2, and right child 3, what is the final returned maximum path sum?

easy

A. 3

B. 6

C. 5

D. 4

Solution

1. Step 1: Trace helper on left child (2):

   left and right children are null, so left=0, right=0, max_sum updated to max(-inf, 2+0+0)=2, returns 2+max(0,0)=2.

2. Step 2: Trace helper on right child (3):

   Similarly, max_sum updated to max(2, 3+0+0)=3, returns 3+max(0,0)=3.

3. Step 3: Trace helper on root (1):

   left=2, right=3, max_sum updated to max(3, 1+2+3)=6, returns 1+max(2,3)=4.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Max path is 2 -> 1 -> 3 with sum 6 [OK]

Hint: Sum includes node plus max gains from both children [OK]

Common Mistakes:

• Returning sum of one child only
• Off-by-one in max_sum update
• Ignoring zero cutoff for negative gains

3. You are given two sorted arrays and need to find the median of their combined elements efficiently without fully merging them. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge both arrays completely and then find the median from the merged array.

B. Use binary search to partition the smaller array and find the correct partition in the other array.

C. Use a two-pointer approach to partially merge elements until the median position is reached.

D. Apply dynamic programming to store medians of subarrays and combine results.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the median of two sorted arrays without fully merging them to achieve better than O(m+n) time.

2. Step 2: Identify the optimal approach

   Binary search on the smaller array to find a partition that balances elements on both sides guarantees O(log(min(m,n))) time, which is optimal.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on partition is the known optimal solution [OK]

Hint: Optimal median uses binary search on smaller array [OK]

Common Mistakes:

• Assuming full merge is necessary
• Using two pointers without binary search
• Confusing DP with median finding

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

5. What is the time complexity of the optimal solution for Word Search II that uses backtracking with a Trie and in-place board modification, assuming the board size is NxM, the number of words is W, and the maximum length of a word is L?

medium

A. O(W * N * M * 4^L) because each word is searched independently

B. O(W * L) for building Trie plus O(N * M * 4^L) for backtracking

C. O(N * M * L * W) because Trie traversal multiplies word length and count

D. O(N * M * 4^L) due to backtracking pruning with Trie prefix checks

Solution

1. Step 1: Identify Trie construction cost

   Building the Trie takes O(W * L) time, inserting each word character by character.

2. Step 2: Analyze backtracking complexity

   Backtracking explores up to 4^L paths from each cell, so O(N * M * 4^L) dominates search time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie build plus backtracking combined yields O(W*L + N*M*4^L) [OK]

Hint: Trie build separate from backtracking cost [OK]

Common Mistakes:

• Confusing independent word search with Trie pruning
• Ignoring Trie build cost
• Multiplying all parameters incorrectly