Shortest Path Visiting All Nodes

🎯

Shortest Path Visiting All Nodes

hardMIXEDGoogleAmazonFacebook

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?

💡 This problem involves finding the shortest path that visits all nodes in a graph, which is challenging because it combines graph traversal with state tracking. Beginners often struggle because it requires managing multiple states simultaneously and understanding how to efficiently represent visited nodes.

📋

Problem Statement

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

💡

Example

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

Output4

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

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

Output4

One shortest path is 0 -> 1 -> 4 -> 2 -> 3, length 4.

• Single node graph → shortest path length is 0
• Graph with nodes connected in a line → path length equals n-1
• Complete graph → shortest path length is n-1
• Graph with cycles → path may revisit nodes but shortest path still minimal

⚠️

Common Mistakes

Not using bitmask to track visited nodes

Cannot efficiently represent visited states, leading to incorrect or inefficient solutions

✅ Use an integer bitmask where each bit represents a node's visited status

Revisiting states without memoization or visited set

Exponential blowup in runtime and possible infinite loops

✅ Use memoization in recursion or visited sets in BFS to avoid repeated work

Using DFS for shortest path without pruning

May find longer paths first and miss shortest path, leading to wrong answers or TLE

✅ Use BFS to guarantee shortest path by exploring states in order of increasing distance

Incorrectly updating visited bitmask (e.g., forgetting to include current node)

States do not reflect actual visited nodes, causing incorrect results

✅ Always update visited bitmask when moving to a neighbor by OR-ing with neighbor's bit

Not starting BFS from all nodes simultaneously

May miss shortest paths that start from nodes other than 0

✅ Initialize BFS queue with all nodes as starting points with their own visited bitmask

🧠

Brute Force (DFS with State Tracking)

💡 This approach exists to build intuition by exploring all possible paths exhaustively. It is impractical for large graphs but helps understand the problem's complexity and why optimization is necessary.

Intuition

Try all possible paths starting from each node, keeping track of visited nodes using a bitmask. Recursively explore neighbors until all nodes are visited, then record the shortest path length.

Algorithm

1. Represent visited nodes using a bitmask integer.
2. For each node, start a DFS that explores all neighbors recursively.
3. At each step, update the visited bitmask and continue until all nodes are visited.
4. Return the minimum path length found among all starting nodes.

💡 Tracking visited nodes with bitmasks and recursive exploration is conceptually simple but leads to exponential time complexity, making it hard to scale.

</>

Code

from typing import List
import sys
sys.setrecursionlimit(10**7)

def shortestPathLength(graph: List[List[int]]) -> int:
    n = len(graph)
    all_visited = (1 << n) - 1
    memo = {}

    def dfs(node: int, visited: int) -> int:
        if visited == all_visited:
            return 0
        if (node, visited) in memo:
            return memo[(node, visited)]
        ans = float('inf')
        for nei in graph[node]:
            next_visited = visited | (1 << nei)
            ans = min(ans, 1 + dfs(nei, next_visited))
        memo[(node, visited)] = ans
        return ans

    res = float('inf')
    for i in range(n):
        res = min(res, dfs(i, 1 << i))
    return res

# Driver code
if __name__ == '__main__':
    graph = [[1,2,3],[0],[0],[0]]
    print(shortestPathLength(graph))  # Output: 4

Line Notes

n = len(graph)Determine the number of nodes to set bitmask size

all_visited = (1 << n) - 1Bitmask representing all nodes visited

memo = {}Cache results to avoid recomputation of states

def dfs(node: int, visited: int) -> int:Recursive function exploring paths from current node with visited state

if visited == all_visited:Base case: all nodes visited, path length zero from here

if (node, visited) in memo:Return cached result to save time

for nei in graph[node]:Explore all neighbors of current node

next_visited = visited | (1 << nei)Mark neighbor as visited in bitmask

ans = min(ans, 1 + dfs(nei, next_visited))Update minimum path length including this step

for i in range(n):Try starting DFS from every node

res = min(res, dfs(i, 1 << i))Track shortest path among all starting points

import java.util.*;

public class Solution {
    private int n;
    private int allVisited;
    private Map<String, Integer> memo = new HashMap<>();

    public int shortestPathLength(int[][] graph) {
        n = graph.length;
        allVisited = (1 << n) - 1;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dfs(graph, i, 1 << i));
        }
        return res;
    }

    private int dfs(int[][] graph, int node, int visited) {
        if (visited == allVisited) return 0;
        String key = node + "," + visited;
        if (memo.containsKey(key)) return memo.get(key);
        int ans = Integer.MAX_VALUE;
        for (int nei : graph[node]) {
            int nextVisited = visited | (1 << nei);
            ans = Math.min(ans, 1 + dfs(graph, nei, nextVisited));
        }
        memo.put(key, ans);
        return ans;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = {{1,2,3},{0},{0},{0}};
        System.out.println(sol.shortestPathLength(graph)); // Output: 4
    }
}

Line Notes

n = graph.lengthInitialize number of nodes

allVisited = (1 << n) - 1Bitmask for all nodes visited

memo = new HashMap<>()Cache to store computed states

for (int i = 0; i < n; i++)Try starting DFS from each node

if (visited == allVisited) return 0Base case: all nodes visited

String key = node + "," + visitedCreate unique key for memoization

if (memo.containsKey(key)) return memo.get(key)Return cached result if available

for (int nei : graph[node])Explore neighbors

int nextVisited = visited | (1 << nei)Mark neighbor visited

ans = Math.min(ans, 1 + dfs(graph, nei, nextVisited))Update minimum path length

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int n, allVisited;
    unordered_map<string, int> memo;

    int dfs(const vector<vector<int>>& graph, int node, int visited) {
        if (visited == allVisited) return 0;
        string key = to_string(node) + "," + to_string(visited);
        if (memo.count(key)) return memo[key];
        int ans = INT_MAX;
        for (int nei : graph[node]) {
            int nextVisited = visited | (1 << nei);
            ans = min(ans, 1 + dfs(graph, nei, nextVisited));
        }
        memo[key] = ans;
        return ans;
    }

public:
    int shortestPathLength(vector<vector<int>>& graph) {
        n = graph.size();
        allVisited = (1 << n) - 1;
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            res = min(res, dfs(graph, i, 1 << i));
        }
        return res;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> graph = {{1,2,3},{0},{0},{0}};
    cout << sol.shortestPathLength(graph) << "\n"; // Output: 4
    return 0;
}

Line Notes

n = graph.size()Get number of nodes

allVisited = (1 << n) - 1Bitmask representing all nodes visited

unordered_map<string, int> memoMemoization cache for states

if (visited == allVisited) return 0Base case: all nodes visited

string key = to_string(node) + "," + to_string(visited)Unique key for memo lookup

if (memo.count(key)) return memo[key]Return cached result if exists

for (int nei : graph[node])Iterate over neighbors

int nextVisited = visited | (1 << nei)Mark neighbor visited in bitmask

ans = min(ans, 1 + dfs(graph, nei, nextVisited))Update minimum path length

for (int i = 0; i < n; i++)Try starting DFS from each node

function shortestPathLength(graph) {
    const n = graph.length;
    const allVisited = (1 << n) - 1;
    const memo = new Map();

    function dfs(node, visited) {
        if (visited === allVisited) return 0;
        const key = node + ',' + visited;
        if (memo.has(key)) return memo.get(key);
        let ans = Infinity;
        for (const nei of graph[node]) {
            const nextVisited = visited | (1 << nei);
            ans = Math.min(ans, 1 + dfs(nei, nextVisited));
        }
        memo.set(key, ans);
        return ans;
    }

    let res = Infinity;
    for (let i = 0; i < n; i++) {
        res = Math.min(res, dfs(i, 1 << i));
    }
    return res;
}

// Driver code
const graph = [[1,2,3],[0],[0],[0]];
console.log(shortestPathLength(graph)); // Output: 4

Line Notes

const n = graph.lengthNumber of nodes in graph

const allVisited = (1 << n) - 1Bitmask for all nodes visited

const memo = new Map()Cache for memoization

if (visited === allVisited) return 0Base case: all nodes visited

const key = node + ',' + visitedUnique key for memo lookup

if (memo.has(key)) return memo.get(key)Return cached result if available

for (const nei of graph[node])Iterate neighbors

const nextVisited = visited | (1 << nei)Mark neighbor visited

ans = Math.min(ans, 1 + dfs(nei, nextVisited))Update minimum path length

for (let i = 0; i < n; i++)Try starting DFS from each node

⏱

Complexity

TimeO(n * 2^n)

SpaceO(n * 2^n)

Each state is defined by current node and visited bitmask, total n * 2^n states. Each state explores neighbors.

💡 For n=12, this means roughly 12 * 4096 = 49,152 states, which is borderline feasible but slow. For n=20, it would be over 20 million states, which is impractical.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is crucial to understand the problem's exponential nature and motivate better solutions.

🧠

BFS with State Compression (Bitmask BFS)

💡 This approach improves over brute force by using BFS to find the shortest path level by level, avoiding deep recursion and exploring states efficiently.

Intuition

Use a queue to perform BFS over states defined by (current node, visited nodes bitmask). Start from all nodes simultaneously and expand until all nodes are visited.

Algorithm

1. Initialize a queue with all nodes as starting points, each with their own visited bitmask.
2. Use a visited set to track (node, visited) states to avoid revisiting.
3. While queue not empty, pop front and explore neighbors, updating visited bitmask.
4. If a state with all nodes visited is reached, return the current path length.

💡 This approach systematically explores all states in order of increasing path length, guaranteeing the shortest path is found first.

</>

Code

from collections import deque
from typing import List

def shortestPathLength(graph: List[List[int]]) -> int:
    n = len(graph)
    all_visited = (1 << n) - 1
    queue = deque()
    visited = set()

    for i in range(n):
        mask = 1 << i
        queue.append((i, mask, 0))  # node, visited mask, distance
        visited.add((i, mask))

    while queue:
        node, mask, dist = queue.popleft()
        if mask == all_visited:
            return dist
        for nei in graph[node]:
            next_mask = mask | (1 << nei)
            if (nei, next_mask) not in visited:
                visited.add((nei, next_mask))
                queue.append((nei, next_mask, dist + 1))

# Driver code
if __name__ == '__main__':
    graph = [[1,2,3],[0],[0],[0]]
    print(shortestPathLength(graph))  # Output: 4

Line Notes

queue = deque()Initialize queue for BFS

visited = set()Track visited states to avoid repeats

for i in range(n)Start BFS from all nodes simultaneously

queue.append((i, mask, 0))Enqueue initial states with distance 0

while queue:Process states in BFS order

node, mask, dist = queue.popleft()Dequeue current state

if mask == all_visited:Check if all nodes visited

for nei in graph[node]:Explore neighbors

next_mask = mask | (1 << nei)Update visited bitmask

if (nei, next_mask) not in visitedAvoid revisiting states

queue.append((nei, next_mask, dist + 1))Enqueue next state with incremented distance

import java.util.*;

public class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int allVisited = (1 << n) - 1;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][1 << n];

        for (int i = 0; i < n; i++) {
            int mask = 1 << i;
            queue.offer(new int[]{i, mask, 0});
            visited[i][mask] = true;
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int node = cur[0], mask = cur[1], dist = cur[2];
            if (mask == allVisited) return dist;
            for (int nei : graph[node]) {
                int nextMask = mask | (1 << nei);
                if (!visited[nei][nextMask]) {
                    visited[nei][nextMask] = true;
                    queue.offer(new int[]{nei, nextMask, dist + 1});
                }
            }
        }
        return -1;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = {{1,2,3},{0},{0},{0}};
        System.out.println(sol.shortestPathLength(graph)); // Output: 4
    }
}

Line Notes

int n = graph.lengthNumber of nodes

int allVisited = (1 << n) - 1Bitmask for all nodes visited

Queue<int[]> queue = new LinkedList<>()Queue for BFS states

boolean[][] visited = new boolean[n][1 << n]Track visited states efficiently

for (int i = 0; i < n; i++)Initialize BFS from all nodes

queue.offer(new int[]{i, mask, 0})Enqueue initial states with distance 0

while (!queue.isEmpty())Process BFS queue

if (mask == allVisited) return distReturn distance when all nodes visited

for (int nei : graph[node])Explore neighbors

if (!visited[nei][nextMask])Avoid revisiting states

queue.offer(new int[]{nei, nextMask, dist + 1})Enqueue next state

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int allVisited = (1 << n) - 1;
        queue<tuple<int,int,int>> q; // node, mask, dist
        vector<vector<bool>> visited(n, vector<bool>(1 << n, false));

        for (int i = 0; i < n; i++) {
            int mask = 1 << i;
            q.emplace(i, mask, 0);
            visited[i][mask] = true;
        }

        while (!q.empty()) {
            auto [node, mask, dist] = q.front(); q.pop();
            if (mask == allVisited) return dist;
            for (int nei : graph[node]) {
                int nextMask = mask | (1 << nei);
                if (!visited[nei][nextMask]) {
                    visited[nei][nextMask] = true;
                    q.emplace(nei, nextMask, dist + 1);
                }
            }
        }
        return -1;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> graph = {{1,2,3},{0},{0},{0}};
    cout << sol.shortestPathLength(graph) << "\n"; // Output: 4
    return 0;
}

Line Notes

int n = graph.size()Number of nodes

int allVisited = (1 << n) - 1Bitmask for all nodes visited

queue<tuple<int,int,int>> qQueue for BFS states with node, mask, distance

vector<vector<bool>> visitedTrack visited states to avoid repeats

for (int i = 0; i < n; i++)Initialize BFS from all nodes

q.emplace(i, mask, 0)Enqueue initial states with distance 0

while (!q.empty())Process BFS queue

if (mask == allVisited) return distReturn distance when all nodes visited

for (int nei : graph[node])Explore neighbors

if (!visited[nei][nextMask])Avoid revisiting states

q.emplace(nei, nextMask, dist + 1)Enqueue next state

function shortestPathLength(graph) {
    const n = graph.length;
    const allVisited = (1 << n) - 1;
    const queue = [];
    const visited = Array.from({length: n}, () => new Array(1 << n).fill(false));

    for (let i = 0; i < n; i++) {
        const mask = 1 << i;
        queue.push([i, mask, 0]);
        visited[i][mask] = true;
    }

    while (queue.length > 0) {
        const [node, mask, dist] = queue.shift();
        if (mask === allVisited) return dist;
        for (const nei of graph[node]) {
            const nextMask = mask | (1 << nei);
            if (!visited[nei][nextMask]) {
                visited[nei][nextMask] = true;
                queue.push([nei, nextMask, dist + 1]);
            }
        }
    }
    return -1;
}

// Driver code
const graph = [[1,2,3],[0],[0],[0]];
console.log(shortestPathLength(graph)); // Output: 4

Line Notes

const n = graph.lengthNumber of nodes

const allVisited = (1 << n) - 1Bitmask for all nodes visited

const queue = []Queue for BFS states

const visited = Array.from({length: n}, () => new Array(1 << n).fill(false))Track visited states

for (let i = 0; i < n; i++)Initialize BFS from all nodes

queue.push([i, mask, 0])Enqueue initial states with distance 0

while (queue.length > 0)Process BFS queue

if (mask === allVisited) return distReturn distance when all nodes visited

for (const nei of graph[node])Explore neighbors

if (!visited[nei][nextMask])Avoid revisiting states

queue.push([nei, nextMask, dist + 1])Enqueue next state

⏱

Complexity

TimeO(n * 2^n)

SpaceO(n * 2^n)

Each state (node, visited bitmask) is processed once in BFS. There are n * 2^n states.

💡 This approach is much faster in practice than brute force recursion because it avoids redundant deep calls and finds shortest paths level by level.

Interview Verdict: Accepted / Optimal for given constraints

This BFS with bitmask approach is the standard optimal solution for this problem and is expected in interviews.

🧠

Bidirectional BFS with State Compression

💡 This approach further optimizes BFS by searching simultaneously from the start and end states, meeting in the middle to reduce search space.

Intuition

Run two BFS traversals: one from all nodes with their initial visited bitmask, and one from the state where all nodes are visited. When the two searches meet, the shortest path length is found.

Algorithm

1. Initialize two queues and visited sets: one from all single-node starts, one from the all-visited state.
2. Alternate expanding states from each queue.
3. If a state appears in both visited sets, return the sum of distances from both sides.
4. Continue until the two searches meet.

💡 By searching from both ends, the number of states explored is drastically reduced, improving performance on larger graphs.

</>

Code

from collections import deque
from typing import List

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

    # Queue elements: (node, visited_mask)
    q1 = deque()
    q2 = deque()

    visited1 = dict()
    visited2 = dict()

    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

    while q1 and q2:
        # Expand from q1
        for _ in range(len(q1)):
            node, mask = q1.popleft()
            dist = visited1[(node, mask)]
            if (node, mask) in visited2:
                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))

        # Expand from q2
        for _ in range(len(q2)):
            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

# Driver code
if __name__ == '__main__':
    graph = [[1,2,3],[0],[0],[0]]
    print(shortestPathLength(graph))  # Output: 4

Line Notes

q1 = deque()Queue for forward BFS

q2 = deque()Queue for backward BFS

visited1 = dict()Visited states for forward BFS

visited2 = dict()Visited states for backward BFS

for i in range(n)Initialize both BFS queues and visited sets

if (node, mask) in visited2Check if forward and backward searches meet

next_mask = mask | (1 << nei)Update visited mask forward

next_mask = mask & ~(1 << nei)Update visited mask backward

visited1[(nei, next_mask)] = dist + 1Mark forward visited

visited2[(nei, next_mask)] = dist + 1Mark backward visited

import java.util.*;

public class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int allVisited = (1 << n) - 1;

        Queue<int[]> q1 = new LinkedList<>();
        Queue<int[]> q2 = new LinkedList<>();

        Map<String, Integer> visited1 = new HashMap<>();
        Map<String, Integer> visited2 = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int mask = 1 << i;
            q1.offer(new int[]{i, mask});
            visited1.put(i + "," + mask, 0);
            q2.offer(new int[]{i, allVisited ^ mask});
            visited2.put(i + "," + (allVisited ^ mask), 0);
        }

        while (!q1.isEmpty() && !q2.isEmpty()) {
            int res = expand(graph, q1, visited1, visited2);
            if (res != -1) return res;
            res = expand(graph, q2, visited2, visited1);
            if (res != -1) return res;
        }
        return -1;
    }

    private int expand(int[][] graph, Queue<int[]> queue, Map<String, Integer> visitedCurr, Map<String, Integer> visitedOther) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            int node = cur[0], mask = cur[1];
            int dist = visitedCurr.get(node + "," + mask);
            if (visitedOther.containsKey(node + "," + mask)) {
                return dist + visitedOther.get(node + "," + mask);
            }
            for (int nei : graph[node]) {
                int nextMask = (visitedCurr == visitedOther) ? (mask | (1 << nei)) : (mask & ~(1 << nei));
                String key = nei + "," + nextMask;
                if (!visitedCurr.containsKey(key)) {
                    visitedCurr.put(key, dist + 1);
                    queue.offer(new int[]{nei, nextMask});
                }
            }
        }
        return -1;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = {{1,2,3},{0},{0},{0}};
        System.out.println(sol.shortestPathLength(graph)); // Output: 4
    }
}

Line Notes

int n = graph.lengthNumber of nodes

int allVisited = (1 << n) - 1Bitmask for all nodes visited

Queue<int[]> q1 = new LinkedList<>()Forward BFS queue

Queue<int[]> q2 = new LinkedList<>()Backward BFS queue

Map<String, Integer> visited1 = new HashMap<>()Forward visited states

Map<String, Integer> visited2 = new HashMap<>()Backward visited states

for (int i = 0; i < n; i++)Initialize BFS queues and visited maps

if (visitedOther.containsKey(node + "," + mask))Check if searches meet

int nextMask = (visitedCurr == visitedOther) ? (mask | (1 << nei)) : (mask & ~(1 << nei))Update mask differently for forward/backward

visitedCurr.put(key, dist + 1)Mark visited in current BFS

queue.offer(new int[]{nei, nextMask})Enqueue next state

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int allVisited = (1 << n) - 1;

        queue<pair<int,int>> q1, q2;
        unordered_map<int,int> visited1, visited2;

        auto encode = [&](int node, int mask) {
            return (mask << 5) | node; // pack node and mask into int
        };

        for (int i = 0; i < n; i++) {
            int mask = 1 << i;
            q1.emplace(i, mask);
            visited1[encode(i, mask)] = 0;
            q2.emplace(i, allVisited ^ mask);
            visited2[encode(i, allVisited ^ mask)] = 0;
        }

        while (!q1.empty() && !q2.empty()) {
            int res = expand(graph, q1, visited1, visited2, encode);
            if (res != -1) return res;
            res = expand(graph, q2, visited2, visited1, encode);
            if (res != -1) return res;
        }
        return -1;
    }

private:
    int expand(const vector<vector<int>>& graph, queue<pair<int,int>>& q, unordered_map<int,int>& visitedCurr, unordered_map<int,int>& visitedOther, function<int(int,int)> encode) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [node, mask] = q.front(); q.pop();
            int dist = visitedCurr[encode(node, mask)];
            if (visitedOther.count(encode(node, mask))) {
                return dist + visitedOther[encode(node, mask)];
            }
            for (int nei : graph[node]) {
                int nextMask = (visitedCurr == visitedOther) ? (mask | (1 << nei)) : (mask & ~(1 << nei));
                int key = encode(nei, nextMask);
                if (!visitedCurr.count(key)) {
                    visitedCurr[key] = dist + 1;
                    q.emplace(nei, nextMask);
                }
            }
        }
        return -1;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> graph = {{1,2,3},{0},{0},{0}};
    cout << sol.shortestPathLength(graph) << "\n"; // Output: 4
    return 0;
}

Line Notes

int n = graph.size()Number of nodes

int allVisited = (1 << n) - 1Bitmask for all nodes visited

queue<pair<int,int>> q1, q2Queues for forward and backward BFS

unordered_map<int,int> visited1, visited2Visited states for both BFS

auto encode = [&](int node, int mask)Pack node and mask into single int for map keys

for (int i = 0; i < n; i++)Initialize BFS queues and visited maps

if (visitedOther.count(encode(node, mask)))Check if searches meet

int nextMask = (visitedCurr == visitedOther) ? (mask | (1 << nei)) : (mask & ~(1 << nei))Update mask differently for forward/backward

visitedCurr[key] = dist + 1Mark visited in current BFS

q.emplace(nei, nextMask)Enqueue next state

function shortestPathLength(graph) {
    const n = graph.length;
    const allVisited = (1 << n) - 1;

    const q1 = [];
    const q2 = [];

    const visited1 = new Map();
    const visited2 = new Map();

    function encode(node, mask) {
        return node + ',' + mask;
    }

    for (let i = 0; i < n; i++) {
        const mask = 1 << i;
        q1.push([i, mask]);
        visited1.set(encode(i, mask), 0);
        q2.push([i, allVisited ^ mask]);
        visited2.set(encode(i, allVisited ^ mask), 0);
    }

    function expand(queue, visitedCurr, visitedOther) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const [node, mask] = queue.shift();
            const dist = visitedCurr.get(encode(node, mask));
            if (visitedOther.has(encode(node, mask))) {
                return dist + visitedOther.get(encode(node, mask));
            }
            for (const nei of graph[node]) {
                const nextMask = visitedCurr === visitedOther ? (mask | (1 << nei)) : (mask & ~(1 << nei));
                const key = encode(nei, nextMask);
                if (!visitedCurr.has(key)) {
                    visitedCurr.set(key, dist + 1);
                    queue.push([nei, nextMask]);
                }
            }
        }
        return -1;
    }

    while (q1.length && q2.length) {
        let res = expand(q1, visited1, visited2);
        if (res !== -1) return res;
        res = expand(q2, visited2, visited1);
        if (res !== -1) return res;
    }
    return -1;
}

// Driver code
const graph = [[1,2,3],[0],[0],[0]];
console.log(shortestPathLength(graph)); // Output: 4

Line Notes

const n = graph.lengthNumber of nodes

const allVisited = (1 << n) - 1Bitmask for all nodes visited

const q1 = []Forward BFS queue

const q2 = []Backward BFS queue

const visited1 = new Map()Forward visited states

const visited2 = new Map()Backward visited states

function encode(node, mask)Create unique key for visited maps

if (visitedOther.has(encode(node, mask)))Check if searches meet

const nextMask = visitedCurr === visitedOther ? (mask | (1 << nei)) : (mask & ~(1 << nei))Update mask differently for forward/backward

visitedCurr.set(key, dist + 1)Mark visited in current BFS

queue.push([nei, nextMask])Enqueue next state

⏱

Complexity

TimeO(n * 2^(n/2))

SpaceO(n * 2^(n/2))

Bidirectional BFS reduces the search depth roughly by half, significantly reducing states explored compared to single BFS.

💡 This approach is more complex but can handle larger graphs faster by meeting in the middle, cutting down exponential growth.

Interview Verdict: Accepted / Advanced optimization

While not always necessary, bidirectional BFS is a powerful technique to mention for optimization in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the BFS with state compression approach is recommended as it is optimal and accepted. Brute force is useful to explain but not to implement fully. Bidirectional BFS is advanced and optional.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with State Tracking)	O(n * 2^n)	O(n * 2^n)	Yes (deep recursion)	Yes (with memo)	Mention only - never code
2. BFS with State Compression	O(n * 2^n)	O(n * 2^n)	No	Yes (store parents)	Code this approach
3. Bidirectional BFS with State Compression	O(n * 2^(n/2))	O(n * 2^(n/2))	No	Yes (more complex)	Mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the BFS with state compression as the optimal solution. Finally, discuss possible optimizations like bidirectional BFS.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force recursive approach with bitmasking to track visited nodes.Explain why brute force is inefficient and introduce BFS with state compression.Discuss how BFS guarantees shortest path by exploring states level by level.Optionally mention bidirectional BFS as an advanced optimization.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of graph traversal, state representation with bitmasks, BFS for shortest paths in state space, and ability to optimize exponential search.

Common Follow-ups

• What if the graph is directed? → Adjust neighbor exploration accordingly.
• Can you reconstruct the actual path? → Store parent states during BFS and backtrack.

💡 These follow-ups test your ability to adapt the solution to variations and extend it to return more information.

🔍

Pattern Recognition

When to Use

1) Problem asks for shortest path visiting all nodes; 2) Graph is unweighted; 3) Need to track visited subsets; 4) Constraints allow bitmasking (n ≤ ~12).

Signature Phrases

shortest path that visits every nodevisit all nodes at least oncegraph traversal with state

NOT This Pattern When

Problems that require simple BFS or DFS without state tracking or problems with large n where bitmasking is infeasible.

Similar Problems

Travelling Salesman Problem - similar bitmask DP approach but weighted graphMinimum Height Trees - also involves graph traversal and state trackingShortest Hamiltonian Path - related to visiting all nodes with shortest path

Practice

1. You are given an array of integers and need to find the length of the longest strictly increasing subsequence (not necessarily contiguous). Which algorithmic approach guarantees an optimal solution with a time complexity better than O(n²)?

easy

A. Sorting the array and then finding the longest consecutive sequence

B. Greedy approach that picks the next larger element whenever possible without backtracking

C. Pure recursion checking all subsequences without memoization

D. Dynamic Programming with binary search to maintain a list of potential subsequence tails

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest strictly increasing subsequence, which is a classic DP problem where greedy alone fails because local choices don't guarantee global optimality.

2. Step 2: Identify optimal approach

   Dynamic Programming combined with binary search maintains a list of smallest possible tails for subsequences of different lengths, achieving O(n log n) time, better than O(n²) DP or exponential brute force.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search + DP is known optimal for LIS [OK]

Hint: Binary search + DP beats naive DP and greedy [OK]

Common Mistakes:

• Assuming greedy always works for subsequence problems
• Confusing sorting with LIS problem
• Ignoring memoization in recursion

2. The following code attempts to find the longest chain of pairs but contains a subtle bug. Identify the line causing incorrect results on some inputs.

medium

A. Line 10: Checking if pair[0] > current_end

B. Line 7: Initializing current_end to negative infinity

C. Line 4: Sorting pairs by their start values

D. Line 12: Updating current_end to pair[1]

Solution

1. Step 1: Analyze sorting step

   Sorting by start values does not guarantee optimal chain selection in greedy approach.

2. Step 2: Impact on chain selection

   Greedy selection after sorting by start can miss longer chains that sorting by end would find.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by end is required for correctness [OK]

Hint: Sort by end, not start, for greedy correctness [OK]

Common Mistakes:

• Sorting by start and expecting greedy to work
• Misunderstanding greedy selection criteria
• Assuming initialization or condition is faulty

3. The following code attempts to solve the Russian Doll Envelopes problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes by width ascending and height ascending

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing element in lis at found index

Solution

1. Step 1: Examine sorting order

   Sorting by width ascending and height ascending causes envelopes with same width but increasing height to be counted incorrectly in LIS.

2. Step 2: Understand LIS requirement

   Heights must be sorted descending for equal widths to avoid counting invalid envelopes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order bug leads to wrong LIS and incorrect nesting count [OK]

Hint: Sort height descending for equal widths to avoid LIS errors [OK]

Common Mistakes:

• Sorting both dimensions ascending instead of height descending
• Misusing bisect functions
• Incorrectly extracting heights

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

5. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and the tree is now a general graph with possible cycles. Which of the following approaches correctly adapts the maximum path sum solution to handle this variant?

hard

A. Use the same DP on tree approach with memoization, ignoring cycles since the graph is connected

B. Convert the graph to a tree by removing edges to break cycles, then apply the original DP on tree solution

C. Perform a DFS with cycle detection and use dynamic programming with visited states to avoid infinite loops, tracking maximum sums on simple paths

D. Use a greedy approach to select the highest value nodes repeatedly until no improvement

Solution

1. Step 1: Understand the impact of cycles

   Allowing node reuse and cycles means paths can be infinite unless cycles are detected and handled.

2. Step 2: Identify correct approach

   DFS with cycle detection and DP with visited states prevents infinite loops and correctly computes max sums on simple paths in graphs.

3. Step 3: Why other options fail

   Original DP assumes tree structure; greedy ignores path connectivity; converting graph to tree loses valid paths.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Cycle-aware DFS with DP is necessary for graphs with cycles [OK]

Hint: Cycle detection plus DP needed for graphs with cycles [OK]

Common Mistakes:

• Ignoring cycles causes infinite loops
• Greedy fails on path connectivity
• Tree DP invalid on graphs