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 balloons, each with a number representing coins. When you burst a balloon, you gain coins equal to the product of the balloon's number and its adjacent balloons' numbers. After bursting, the balloon disappears, and the neighbors become adjacent. Which algorithmic approach guarantees finding the maximum coins you can collect by bursting all balloons in an optimal order?

easy

A. A greedy algorithm that always bursts the balloon with the smallest number first

B. Sorting balloons and bursting them in ascending order to maximize adjacent products

C. A simple depth-first search without memoization to explore all bursting sequences

D. Dynamic programming that considers all subproblems of bursting balloons between indices and uses bottom-up tabulation

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing coins by choosing the order of bursting balloons, where each burst depends on neighbors that change dynamically.

2. Step 2: Identify algorithmic pattern

   Greedy or sorting approaches fail because the optimal choice depends on future bursts. DFS without memoization is exponential and inefficient. Dynamic programming with bottom-up tabulation systematically solves overlapping subproblems and ensures optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP solves all subproblems optimally [OK]

Hint: Optimal order depends on future bursts, so DP is needed [OK]

Common Mistakes:

• Assuming greedy bursting works
• Ignoring overlapping subproblems
• Not using memoization

2. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by sorting envelopes by width and picking the tallest envelope at each step.

B. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search.

C. Dynamic programming with a 2D table tracking all pairs of envelopes to find the longest chain.

D. Use a graph and find the longest path by topological sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires strict increasing order in both width and height for nesting envelopes.

2. Step 2: Identify optimal approach

   Sorting by width ascending and height descending ensures envelopes with the same width do not interfere. Then LIS on heights finds the longest chain efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + LIS with binary search is the known optimal approach [OK]

Hint: Sort width asc, height desc, then LIS on heights [OK]

Common Mistakes:

• Using greedy picking tallest envelope only
• Applying LIS on widths instead of heights
• Using DP without sorting properly

3. Suppose the histogram bars can be reused multiple times to form rectangles (i.e., you can select the same bar multiple times consecutively). Which modification to the single pass stack-based algorithm correctly handles this variant?

hard

A. Use the same stack-based approach but remove the sentinel bar

B. Switch to a dynamic programming approach that counts repeated bars explicitly

C. Modify width calculation to include repeated bars by removing '-1' in width formula

D. No modification needed; the original algorithm already handles reuse

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means rectangles can extend beyond contiguous bars, breaking the assumption that each bar is used once in a contiguous segment.

2. Step 2: Why stack approach fails

   The stack-based method relies on contiguous bars and their indices; it cannot track multiple uses of the same bar or non-contiguous reuse.

3. Step 3: Correct approach

   A dynamic programming approach that explicitly counts repeated bars or uses a different state representation is needed to handle reuse correctly.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stack method assumes single use; DP needed for reuse [OK]

Hint: Reuse breaks contiguous assumption; DP needed [OK]

Common Mistakes:

• Thinking original stack method handles reuse
• Trying to fix width formula only
• Removing sentinel bar to fix reuse

4. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column conflicts are ignored), but diagonal conflicts still apply. Which modification to the bitmask backtracking algorithm correctly adapts to this variant?

hard

A. Use a greedy approach placing queens row-wise ignoring conflicts

B. Remove the column bitmask cols from the pruning condition and keep diagonal bitmasks unchanged

C. Remove diagonal bitmasks and only use column bitmask to prune

D. Keep all bitmasks unchanged but allow multiple queens per column by skipping column checks

Solution

1. Step 1: Identify which constraints remain

   Column conflicts are ignored, so cols bitmask should not prune positions.

2. Step 2: Modify pruning condition

   Remove cols from available_positions = mask & ~(cols | pos_diags | neg_diags), keeping diagonal bitmasks to prune invalid diagonals.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Removing column mask allows multiple queens per column [OK]

Hint: Remove column mask to allow multiple queens per column [OK]

Common Mistakes:

• Removing diagonal masks breaks diagonal checks
• Ignoring pruning leads to exponential blowup
• Using greedy approach fails correctness

5. Suppose the problem is modified so that envelopes can be reused multiple times in the nesting sequence. Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Keep the sorting step, but replace LIS with a dynamic programming approach that allows repeated elements by using <= comparisons.

B. Use the same sorting and LIS with binary search approach, but allow bisect_right instead of bisect_left to handle duplicates.

C. Sort envelopes by width ascending and height descending, then use a DP approach similar to unbounded knapsack allowing reuse.

D. Remove sorting and use a greedy approach to pick envelopes repeatedly based on height only.

Solution

1. Step 1: Understand reuse impact

   Allowing reuse breaks LIS assumptions since elements can be repeated multiple times.

2. Step 2: Adapt algorithm

   Sorting still helps, but LIS must be replaced by a DP approach similar to unbounded knapsack that allows multiple uses of the same envelope.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP with reuse and sorting is correct adaptation [OK]

Hint: Reuse means LIS no longer applies; use unbounded knapsack DP [OK]

Common Mistakes:

• Trying to fix LIS with bisect_right
• Using <= in LIS but still only one use per envelope
• Ignoring sorting or using greedy