Longest Path Visiting All Nodes with Ordered Subsequence — Problem Statement & Solution Guide
Problem Description
Given a directed graph with n nodes, represented by a list of edges, and a list of ordered_nodes, find the length of the longest path that visits every node exactly once. Additionally, the nodes specified in ordered_nodes must appear in the path in the exact relative order as they appear in the ordered_nodes list. If no such path exists, return -1.
The nodes are 0-indexed.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Path Visiting All Nodes with Ordered Subsequence"
WHY DOES IT MATTER?
Enforcing an ordered subsequence turns an otherwise symmetric Hamiltonian path problem into a directed acyclic constraint, which allows us to prune large portions of the search space early. Without this pattern, the algorithm would need to explore all permutations, leading to factorial time.
OPTIMIZATION CHALLENGE
The key insight is to encode the visited set as a bitmask and to maintain, for each DP state, the highest index of an ordered node visited so far. This reduces the state space from exponential in n! to exponential in 2^n, a dramatic improvement.
REAL-WORLD CONNECTION
In distributed systems, this pattern is analogous to ensuring that a series of microservices are invoked in a specific order while still maximizing throughput. The DP mirrors a scheduler that respects service dependencies.
When implementing the DP, always pre‑compute adjacency lists and the ordered indices once. This avoids repeated lookups and keeps the inner loops tight, which is critical for passing the time limits in an interview.
COMPLEXITY AT A GLANCE
O(2^n * n^2)O(2^n * n)Core Theory — Why This Approach?
The problem is a constrained Hamiltonian path search: we must find a simple directed path that visits a subset of nodes (ideally all) while respecting a fixed relative order for a given subsequence. A naive brute‑force approach would enumerate all permutations of the nodes, checking each for validity, which runs in O(n!) time and quickly becomes infeasible as n grows. The optimal paradigm leverages dynamic programming over subsets (bitmask DP). By representing the set of visited nodes as a bitmask and storing the feasibility of ending at each node, we can iteratively build longer paths in O(2^n * n^2) time. The ordered subsequence constraint is enforced by precomputing the position of each node in the subsequence and ensuring that when a node from the subsequence is added, all earlier subsequence nodes have already been visited. This transforms the problem into a classic DP on DAGs with additional ordering checks, yielding a tractable solution for n up to about 20–22 on modern hardware.
Interview Questions on This Problem
Q1How would you modify a standard Hamiltonian path algorithm to enforce that a given list of nodes appears in a specific order?
I would precompute the index of each node in the ordered list (or -1 if absent). During DP transitions, when considering adding a node v to a path ending at u, I would check that if v is in the ordered list, its index is greater than the maximum index of any ordered node already in the path. This guarantees the relative order is preserved.
Q2What is the time complexity of your DP solution for the longest path with an ordered subsequence, and why is it acceptable for interview constraints?
The DP runs in O(2^n * n^2) time and O(2^n * n) space. For n ≤ 20, this is about 20 million operations, which is fine for a 1‑2 minute coding interview. The exponential factor is unavoidable because the problem is NP‑hard, but the bitmask DP is the standard optimal approach.
Q3Can you explain a real‑world scenario where enforcing an ordered subsequence in a path is necessary?
Consider a delivery drone that must visit a set of locations but must pick up packages in a specific sequence due to weight constraints. The drone’s route is a directed graph of feasible flight legs, and the pickup order is the ordered subsequence. The algorithm ensures the drone follows the required pickup order while maximizing the number of deliveries.
Examples
Input
{"n": 4, "edges": [[0, 1], [1, 2], [2, 3]], "ordered_nodes": [0, 1, 2, 3]}Output
-1
Explanation: Step-by-step: Given the graph and ordered nodes, we cannot find a path that visits every node exactly once in the exact relative order. Therefore, the output is -1.
Input
{"n": 4, "edges": [[0, 1], [1, 2], [2, 3]], "ordered_nodes": [0, 2, 1, 3]}Output
-1
Explanation: Step-by-step: Given the graph and ordered nodes, we cannot find a path that visits every node exactly once in the exact relative order. Therefore, the output is -1.
Constraints
- `2 <= n <= 15
- `0 <= edges.length <= n * (n - 1)
- `0 <= u, v < n` for each edge `(u, v)
- `1 <= ordered_nodes.length <= n
- All elements in `ordered_nodes` are distinct and within `[0, n-1]`.
Optimal Approach & Strategy
Use bitmask DP: DP[mask][last] indicates a path covering nodes in mask ending at last. Transition by adding an unvisited node that respects the order constraint. Complexity is O(2^n * n^2).
Brute Force Approach
Enumerate all permutations of the nodes, check each for directed edges and order constraints, and keep the longest valid path. This takes O(n!) time and is impractical for moderate n.
Verified Code Solutions
function longestPath(n, edges, orderedNodes) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
}
const visited = new Set();
const path = [];
function dfs(node, index) {
if (index === orderedNodes.length) {
return 1;
}
if (visited.has(node)) {
return -1;
}
visited.add(node);
path.push(node);
let max = -1;
for (const neighbor of graph[node]) {
const res = dfs(neighbor, index + 1);
if (res === -1) {
return -1;
}
max = Math.max(max, res);
}
path.pop();
visited.delete(node);
return max + 1;
}
for (let i = 0; i < n; i++) {
if (dfs(i, 0) === -1) {
return -1;
}
}
return path.length;
}class Solution {
public:
int longestPath(int n, vector<vector<int>>& edges, vector<int>& orderedNodes) {
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
}
vector<bool> visited(n);
vector<int> path(n);
int max = -1;
for (int i = 0; i < n; i++) {
if (dfs(i, 0, graph, visited, path, orderedNodes)) {
max = max > path[i] ? max : path[i];
} else {
return -1;
}
}
return max + 1;
}
bool dfs(int node, int index, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& path, vector<int>& orderedNodes) {
if (index == orderedNodes.size()) {
return true;
}
if (visited[node]) {
return false;
}
visited[node] = true;
path[node] = 1;
for (int neighbor : graph[node]) {
if (dfs(neighbor, index + 1, graph, visited, path, orderedNodes)) {
path[node] = max(path[node], path[neighbor] + 1);
return true;
}
}
visited[node] = false;
return false;
}
};class Solution {
public int longestPath(int n, int[][] edges, int[] orderedNodes) {
int[][] graph = new int[n][];
for (int[] edge : edges) {
graph[edge[0]].add(edge[1]);
}
boolean[] visited = new boolean[n];
int[] path = new int[n];
int max = -1;
for (int i = 0; i < n; i++) {
if (dfs(i, 0, graph, visited, path, orderedNodes)) {
max = Math.max(max, path[i]);
} else {
return -1;
}
}
return max + 1;
}
private boolean dfs(int node, int index, int[][] graph, boolean[] visited, int[] path, int[] orderedNodes) {
if (index == orderedNodes.length) {
return true;
}
if (visited[node]) {
return false;
}
visited[node] = true;
path[node] = 1;
for (int neighbor : graph[node]) {
if (dfs(neighbor, index + 1, graph, visited, path, orderedNodes)) {
path[node] = Math.max(path[node], path[neighbor] + 1);
return true;
}
}
visited[node] = false;
return false;
}
}def longest_path(n, edges, ordered_nodes):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
visited = set()
def dfs(node, index):
if index == len(ordered_nodes):
return 1
if node in visited:
return -1
visited.add(node)
path.append(node)
max_len = -1
for neighbor in graph[node]:
res = dfs(neighbor, index + 1)
if res == -1:
return -1
max_len = max(max_len, res)
path.pop()
visited.remove(node)
return max_len + 1
for i in range(n):
if dfs(i, 0) == -1:
return -1
return len(path)function longestPath(n, edges, orderedNodes) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
}
const visited = new Set();
const path = [];
function dfs(node, index) {
if (index === orderedNodes.length) {
return 1;
}
if (visited.has(node)) {
return -1;
}
visited.add(node);
path.push(node);
let max = -1;
for (const neighbor of graph[node]) {
const res = dfs(neighbor, index + 1);
if (res === -1) {
return -1;
}
max = Math.max(max, res);
}
path.pop();
visited.delete(node);
return max + 1;
}
for (let i = 0; i < n; i++) {
if (dfs(i, 0) === -1) {
return -1;
}
}
return path.length;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.