Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Every edge has the same weight (6), so the shortest path is just the fewest edges — that is plain BFS. Run one BFS from the source, record each node's hop count, and multiply by 6. Unreached nodes report -1. O(V + E).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you spot that uniform edge weights collapse a 'shortest path' question down to BFS, instead of defaulting to Dijkstra and paying an unnecessary log factor.
Where candidates slip
Using Dijkstra (correct but slower) when BFS suffices, or overwriting a node's distance on a later, longer path because the visited check is missing.
How to stand out
Say out loud 'all weights equal, so BFS by hop count is optimal', use the dist array as the visited set, and note you can apply the ×6 factor once at the end.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSingle-source shortest pathAll edge weights equal?YesNoExplore the full treeCollapse the tree
How to read it:From source 1: layer 1 nodes cost 6, layer 2 cost 12, layer 3 cost 18.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Dijkstra with a Min-Heap (Baseline)
1Hint 1Explore hintHide hint
If you did not notice the weights are equal, the safe default for non-negative weights is Dijkstra. What does it cost here?
2Hint 2Explore hintHide hint
Treat every edge as weight 6, push (distance, node) onto a min-heap, and relax neighbors as usual.
3Hint 3Explore hintHide hint
Now ask: does the heap ever reorder nodes differently from BFS, given all weights are identical? It does not — so the log factor buys nothing.
A · Core idea
Dijkstra is the reflex for non-negative weighted shortest paths, and it certainly works here — but it is the wrong tool economically.
Why it is correct. With weight 6 on every edge, Dijkstra finalizes nodes in increasing distance, which is 6 × hop count. The dist array it produces is exactly the answer. Nothing about equal weights breaks the greedy invariant.
Why it is wasteful. A min-heap exists to break ties in which unfinalized node is closest when distances differ. But when every edge weighs the same, the node with the fewest hops is always the closest, and BFS already pops nodes in that order using a plain FIFO queue — no priority comparisons, no log V per operation. So Dijkstra does the same work as BFS plus an unnecessary heap.
What to say in the interview. Naming Dijkstra shows breadth, but immediately add: 'since all weights are equal, the heap degenerates — BFS gives the same result in O(V + E).' That observation is the point of the problem.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2],[1,3]], s = 1Array state
init
dist[s] = 0, rest ∞
6 6 -1C · Code with teaching comments
Reference implementation previewpublic int[] shortestReach(int n, int[][] edges, int s) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]);Explore the full codeHide the full code
D · Why it works and complexityO((V + E) log V) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Equal edge weights are the signal to downgrade from Dijkstra to BFS. The heap only earns its keep when distances can differ between competing frontier nodes.
ComplexityO((V + E) log V) time, O(V + E) space — Standard Dijkstra: O(E) heap pushes each costing O(log V), plus V pops → O((V + E) log V). Correct, but the log V factor is pure overhead when every weight is the same.
E · Edge cases and pitfalls3Reaching for Dijkstra by reflex without noticing the equal weights — slower than needed.Explore edge casesHide edge cases
Pitfalls
- Reaching for Dijkstra by reflex without noticing the equal weights — slower than needed.
- Forgetting the stale-entry skip if you do use a heap — re-relaxes finalized nodes.
- Including the source in the output array.
Approach 2 of 2 · Optimal
Plain BFS, Scale by 6 (Optimal)
1Hint 1Explore hintHide hint
Since every edge costs 6, the cheapest path is the one with the fewest edges. What classic traversal visits nodes in increasing hop count?
2Hint 2Explore hintHide hint
BFS: a FIFO queue, marking each node's distance the first time it is dequeued's neighbor. Set dist[v] = dist[u] + 6 on first reach.
3Hint 3Explore hintHide hint
Use the dist array (initialized to -1) as the visited marker — a node with dist still -1 is unseen. Output all nodes except the source.
A · Core idea
BFS is exactly the right engine because the graph is unweighted in the sense that matters: every edge contributes the same cost.
Why BFS gives shortest paths here. BFS dequeues nodes in non-decreasing hop order — all nodes at 1 hop, then all at 2 hops, and so on. The first time a node is reached, it is reached by a path with the minimum number of edges. Since each edge is worth 6, that minimum-hop path is also the minimum-cost path. There is never a need to revisit a node with a better distance, which is precisely what makes a plain queue (no priority) sufficient.
Why the dist array doubles as the visited set. Initialize every distance to -1. A node still holding -1 has not been reached, so the condition dist[v] == -1 both tests 'unseen' and is the value we ultimately report for unreachable nodes. Setting dist[v] = dist[u] + 6 on first contact marks it visited and records its distance in one step — no separate boolean array.
Why the traversal is iterative. BFS runs off a queue, so there is no recursion and no risk of a stack overflow even with 10⁵ nodes in a single long chain. (A recursive DFS would not give shortest paths anyway, and would risk the stack.)
Applying the ×6. You can add 6 per edge during the BFS (as shown) or run BFS in raw hops and multiply at the end — both produce identical results. Doing it inline keeps the dist array directly reportable.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, edges = [[1,2],[2,3],[3,4]], s = 1Array state
init
dist[1] = 0, rest -1
6 12 18 -1C · Code with teaching comments
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
The whole optimization is recognizing that equal weights reduce 'shortest path' to 'fewest edges'. Once you see that, the priority queue evaporates and a FIFO queue does the job in linear time.
ComplexityO(V + E) time, O(V + E) space — Each vertex is enqueued at most once and each edge is examined at most twice (once from each endpoint) → O(V + E). The dist array is O(V); the adjacency list is O(V + E).
E · Edge cases and pitfalls7n = 1, edges = [], s = 1 — Only the source exists; output is empty (no other nodes).Explore edge casesHide edge cases
Edge cases handled
n = 1, edges = [], s = 1Only the source exists; output is empty (no other nodes).disconnected nodeNever enqueued, stays -1 in the dist array, reported as -1.duplicate edge [1,2] twiceSecond time, node 2 already has a distance → visited check skips it. Harmless.
Pitfalls
- Overwriting dist[v] on a later, longer path — guard with the dist[v] == -1 check.
- Using DFS, which does not visit in distance order and gives wrong shortest paths.
- Including the source node in the output array.
- Recursing for BFS — unnecessary; a queue is both simpler and stack-safe.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] shortestReach(int n, int[][] edges, int s) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Missing the visited guard
Without checking dist[v] == -1 first, a node reached again on a longer path gets its correct distance overwritten, and it may be enqueued repeatedly, breaking both correctness and the O(V + E) bound.
Explore the code comparisonHide the code comparison
Missing the visited guard
Without checking dist[v] == -1 first, a node reached again on a longer path gets its correct distance overwritten, and it may be enqueued repeatedly, breaking both correctness and the O(V + E) bound.
Don't write this
for v in adj[u]:
dist[v] = dist[u] + 6 # overwrites and re-enqueues
queue.append(v)Write this instead
for v in adj[u]:
if dist[v] == -1: # only the first (shortest) arrival
dist[v] = dist[u] + 6
queue.append(v)2Using DFS for shortest path
DFS dives along one branch before exploring others, so the first time it reaches a node is not necessarily by the fewest edges. Only BFS visits in non-decreasing distance order.
Explore the code comparisonHide the code comparison
Using DFS for shortest path
DFS dives along one branch before exploring others, so the first time it reaches a node is not necessarily by the fewest edges. Only BFS visits in non-decreasing distance order.
Don't write this
void dfs(int u, int d) {
dist[u] = d;
for (int v : adj.get(u))
if (dist[v] == -1) dfs(v, d + 6); // not shortest, and risks stack overflow
}Write this instead
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(s);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj.get(u))
if (dist[v] == -1) { dist[v] = dist[u] + 6; queue.offer(v); }
}3Forgetting the ×6 scaling
The output must be distance, not hop count. Reporting raw hops gives 1, 2, 3 instead of 6, 12, 18.
Explore the code comparisonHide the code comparison
Forgetting the ×6 scaling
The output must be distance, not hop count. Reporting raw hops gives 1, 2, 3 instead of 6, 12, 18.
Don't write this
dist[v] = dist[u] + 1 # hop count, not distanceWrite this instead
dist[v] = dist[u] + 6 # each edge weighs 6Revise
Carry the pattern into the interview
Pattern to remember
Single-source BFS, then scale hop count by the uniform edge weight
Code pattern to memorize
dist[src] = 0, queue = [src]
while queue:
u = dequeue
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 6 # uniform edge weight
enqueue v
output dist[i] for every i != src (-1 if unreached)Rules to remember
- 1All edges weigh the same, so BFS by hop count is exact — do not reach for Dijkstra.
- 2Multiply by the fixed edge weight (6) either inside BFS (
dist[u] + 6) or once at the end — both are equivalent. - 3Use the
distarray itself as the visited marker:-1means unseen, anything else means finalized. - 4BFS finalizes a node the first time it is reached; never overwrite an already-set distance.
- 5Exclude the source from the output — HackerRank asks for distances to the other
n − 1nodes.
Use this pattern when
- Single-source shortest path where **every edge costs the same**
- You only need hop counts (optionally scaled by a constant)
- Unweighted (or uniform-weight) graph, possibly disconnected
- Reachability plus distance from one fixed start
Choose another pattern when
- Edges have differing weights → Dijkstra with a min-heap
- Negative edge weights → Bellman-Ford
- All-pairs distances needed → Floyd-Warshall (small dense) or BFS from each node
- You need the closest pair among a set, not from one source → multi-source BFS
Interview takeaway
When edges share one weight, a min-heap is wasted machinery: BFS already visits nodes in distance order. Scaling the hop count by the constant weight at the end gives the exact answer in O(V + E).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSingle-Source BFS for Uniform-Weight Shortest Path. Recognize it whenever every edge costs the same (or is unweighted): BFS visits in distance order, so a plain queue replaces a min-heap. Scale the hop count by the constant weight. The same engine powers Snakes and Ladders, Word Ladder, and Rotting Oranges.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Dijkstra's Shortest PathOnce edge weights differ, swap the FIFO queue for a min-heap.
- Find the Nearest CloneMulti-source BFS — start the search from many nodes at once instead of one.
- Snakes and Ladders: The Quickest Way UpBFS where moves (dice rolls) are the uniform-weight edges on a board graph.
- 0-1 BFSComing soonWhen weights are only 0 or 1, a deque-based BFS still beats Dijkstra.