Minimum Directed Hops — Problem Statement & Solution Guide
Problem Description
You are provided with a directed graph defined by an adjacency list adj, where adj[i] contains the indices of all nodes directly reachable from node i. Given a starting node start and a target node end, determine the minimum number of edges (hops) required to traverse from start to end. If no path exists, return -1. Note that if start is identical to end, the minimum number of hops is 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimum Directed Hops"
WHY DOES IT MATTER?
Shortest‑path in unweighted directed graphs is a foundational pattern that appears in routing, social‑network analysis, and dependency resolution. Mastering BFS for hop count equips engineers to solve a wide range of reachability and minimum‑step problems efficiently.
OPTIMIZATION CHALLENGE
The key insight is to treat the graph as a layered structure and stop as soon as the target appears in the current layer. By marking nodes visited the first time they are enqueued, we avoid redundant traversals and guarantee linear time, which is the optimal bound for any algorithm that must inspect each reachable edge.
REAL-WORLD CONNECTION
Think of a package moving through a logistics network where each hub forwards the parcel to specific next‑hubs. Determining the fewest hand‑offs from origin to destination mirrors the minimum directed hops problem, and BFS models the wave‑like propagation of the parcel through the network.
During an interview, code the BFS with a simple queue (ArrayDeque in Java, collections.deque in Python) and a distance array initialized to -1. Increment distance when you push a neighbor; this eliminates the need for a separate level counter and keeps the implementation clean and bug‑free.
COMPLEXITY AT A GLANCE
O(V + E)O(V)Core Theory — Why This Approach?
The problem of finding the minimum number of directed hops between two vertices in a graph is a classic single‑source shortest‑path problem where each edge has uniform weight (typically weight = 1). The most natural formulation is a breadth‑first search (BFS) on the directed adjacency list because BFS explores vertices in layers: all nodes reachable in one hop, then two hops, and so on. This guarantees that the first time we encounter the target node we have used the fewest possible edges. Naïve approaches such as depth‑first search (DFS) or exhaustive enumeration of all paths quickly become infeasible: the number of simple paths can grow exponentially with the number of vertices, leading to time‑outs and stack overflows on large graphs (|V| up to 10⁵ or more). Moreover, recursive DFS does not naturally produce the shortest‑hop count when edge weights are uniform. The optimal paradigm therefore leverages BFS combined with a visited set (or distance array) to avoid revisiting nodes, achieving linear time relative to the size of the graph (O(V + E)). This approach scales to massive directed networks while preserving correctness.
When implementing BFS for directed graphs, it is crucial to respect edge directionality: a node u can only traverse to v if v appears in adj[u]. The algorithm initializes a queue with the start node, marks it visited, and iteratively dequeues a node, enqueues all its unvisited neighbors, and records the distance (hop count) as the parent’s distance plus one. If the queue empties without reaching the end node, the graph contains no directed path from start to end, and the answer is -1. This linear‑time solution also uses O(V) auxiliary space for the visited/dist array and the queue, which is optimal because any algorithm must at least examine each vertex reachable from the start.
Interview Questions on This Problem
Q1How would you modify the BFS solution to also return the actual path (list of node indices) from start to end?
Maintain a predecessor array pred[] where pred[v] = u when we first discover v from u. After BFS finishes and end is reached, reconstruct the path by backtracking from end to start using pred and then reverse the list. This adds O(V) space but does not change the O(V+E) time complexity.
Q2If each edge had a non‑negative weight, which algorithm would replace BFS to compute the minimum hop cost, and why?
Dijkstra's algorithm would replace BFS because it handles arbitrary non‑negative edge weights while still guaranteeing the shortest‑path cost. BFS only works when all edge weights are equal; Dijkstra uses a priority queue to always expand the currently cheapest frontier, preserving optimality.
Q3In a massive graph stored in a distributed key‑value store, how can you efficiently compute the minimum directed hops without pulling the entire adjacency list into memory?
Implement a level‑synchronous parallel BFS (also known as frontier‑based BFS) where each level's frontier nodes are processed in parallel across workers. Workers fetch adjacency lists for their frontier nodes on‑demand, exchange newly discovered nodes for the next level, and use a distributed visited set (e.g., Bloom filter or sharded hash) to avoid duplicates. This reduces memory footprint and leverages data locality.
Examples
Input
adj = [[1, 2], [2], [3], []], start = 0, end = 3
Output
3
Explanation: The shortest path is 0 -> 1 -> 2 -> 3. This requires traversing 3 edges. Therefore, the minimum number of hops is 3.
Input
adj = [[1, 3], [2], [3], []], start = 0, end = 3
Output
1
Explanation: Node 0 has direct edges to both 1 and 3. Since 3 is directly reachable from 0, the path is 0 -> 3. This requires only 1 hop.
Input
adj = [[1], [2], [0], []], start = 0, end = 3
Output
-1
Explanation: From node 0, we can reach 1, then 2, then back to 0. Node 3 is isolated and has no incoming edges from the component containing 0. Thus, no path exists, and the result is -1.
Input
adj = [[], [], []], start = 1, end = 1
Output
0
Explanation: The start node is the same as the end node. By definition, zero hops are required to remain at the same node.
Constraints
- 1 <= adj.length <= 10^4
- 0 <= start, end < adj.length
- 0 <= adj[i].length <= adj.length - 1
- All values in adj[i] are distinct integers in the range [0, adj.length - 1]
Optimal Approach & Strategy
Run a breadth‑first search from the start node, marking visited nodes and recording distance; stop when the end node is dequeued. This yields the minimum hop count in linear time.
Brute Force Approach
Enumerate every possible path from start to end using depth‑first search and keep track of the shortest length; this quickly explodes combinatorially. It also risks infinite recursion on cycles without extra checks.
Verified Code Solutions
function minHops(edges, src, dst) { if (src === dst) return 0; const queue = [[src, 0]]; const visited = new Set(); while (queue.length > 0) { const [node, hops] = queue.shift(); if (node === dst) return hops; for (const neighbor of edges[node]) { if (!visited.has(neighbor)) { queue.push([neighbor, hops + 1]); visited.add(neighbor); } } } return -1; }class Solution {
public:
int minHops(vector<vector<int>>& edges, int src, int dst) {
if (src == dst) return 0;
queue<pair<int, int>> q;
q.push({src, 0});
unordered_set<int> visited;
while (!q.empty()) {
int node = q.front().first;
int hops = q.front().second;
q.pop();
if (node == dst) return hops;
for (int neighbor : edges[node]) {
if (visited.find(neighbor) == visited.end()) {
q.push({neighbor, hops + 1});
visited.insert(neighbor);
}
}
}
return -1;
}
};import java.util.Queue;
import java.util.LinkedList;
import java.util.HashSet;
public class Solution {
public int minHops(int[][] edges, int src, int dst) {
if (src == dst) return 0;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {src, 0});
HashSet<Integer> visited = new HashSet<>();
while (!queue.isEmpty()) {
int[] nodeHops = queue.poll();
int node = nodeHops[0];
int hops = nodeHops[1];
if (node == dst) return hops;
for (int neighbor : edges[node]) {
if (!visited.contains(neighbor)) {
queue.offer(new int[] {neighbor, hops + 1});
visited.add(neighbor);
}
}
}
return -1;
}
}from collections import deque
def min_hops(edges, src, dst):
if src == dst: return 0
queue = deque([(src, 0)])
visited = set()
while queue:
node, hops = queue.popleft()
if node == dst: return hops
for neighbor in edges[node]:
if neighbor not in visited:
queue.append((neighbor, hops + 1))
visited.add(neighbor)
return -1function minHops(edges, src, dst) { if (src === dst) return 0; const queue = [[src, 0]]; const visited = new Set(); while (queue.length > 0) { const [node, hops] = queue.shift(); if (node === dst) return hops; for (const neighbor of edges[node]) { if (!visited.has(neighbor)) { queue.push([neighbor, hops + 1]); visited.add(neighbor); } } } return -1; }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.