Abstract / Summary

Find the number of different ways to reach a destination using given steps and movement rules.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (700k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Graph Theory
• Shortest Path
• Topological Sort

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a method countPaths that computes the number of distinct shortest-time routes from intersection 0 to intersection n-1 in a weighted undirected graph. The graph is described by roads, each entry containing two endpoints and the travel time between them. The algorithm employs a priority queue (min-heap) to explore nodes in order of increasing accumulated travel time, aggregating ways to reach each node that share the same earliest arrival time.

Data structures

The adjacency list is built with a defaultdict(list) named next. For every road (a, b, time) the code stores a tuple (b, time) in next[a] and a symmetric tuple (a, time) in next[b]. This representation enables constant-time iteration over all outgoing edges of a given intersection.

next = defaultdict(list)
for a, b, time in roads:
    next[a].append((b, time))
    next[b].append((a, time))

A list todo serves as the heap, initially containing a single entry [0, 0, 1] representing zero elapsed time, the start intersection 0, and one way to be there. The heap invariant is maintained by heappush and heappop. A set seen records intersections that have already been processed at their minimal arrival time, guaranteeing that each node is expanded at most once.

todo = [[0, 0, 1]]   # min-heap: time, intersection, ways
seen = set()

Main loop

The algorithm enters an infinite loop that terminates only when the destination is reached. At each iteration it extracts the smallest time value from the heap (now). All entries in the heap that share this exact time are removed together, and their ways are summed per intersection in a temporary defaultdict(int) called same. This batch processing ensures that multiple paths arriving at the same node at the same earliest time are combined before any further expansion.

while True:
    now = todo[0][0]
    same = defaultdict(int)
    while todo and todo[0][0] == now:
        time, intersection, ways = heappop(todo)
        same[intersection] += ways
        seen.add(intersection)

After the batch is collected, the code iterates over each intersection s in same. The number of ways is reduced modulo 1_000_000_007 to keep the result within integer limits. If the current intersection equals the target (n - 1), the method returns the modulo-adjusted count, concluding the search because the earliest possible arrival time for the destination has been found.

for s in same:
    ways = same[s] % 1_000_000_007
    if s == n - 1:
        return ways

For every neighbor other of s that has not yet been marked as seen, a new heap entry is pushed. The new entry records the cumulative time (now + time), the neighbor identifier, and the aggregated ways to reach s. By postponing insertion of nodes already seen, the algorithm avoids revisiting intersections via longer routes.

    for other, time in next[s]:
        if other not in seen:
            heappush(todo, (now + time, other, ways))

Edge case handling

The code implicitly handles several edge conditions:

• When the graph contains multiple parallel edges between the same pair of intersections, each edge is stored separately in the adjacency list, allowing the algorithm to consider all possible travel times.
• If there are several distinct shortest-time paths that converge on the same intermediate intersection, the batch aggregation (same[intersection] += ways) correctly sums the ways before further expansion, ensuring that the count reflects all combinatorial possibilities.
• The modulo operation applied to ways before returning guarantees that the final answer conforms to the required numeric range even when the raw count exceeds typical integer limits.
• The seen set prevents the algorithm from processing a node after its minimal arrival time has been established, which also covers the scenario where a node could be reachable via a zero-time cycle (if such a road existed) by ensuring that only the first (shortest) occurrence is considered.

Performance considerations

The design leverages a min-heap to always expand the currently reachable node(s) with the smallest accumulated travel time. By extracting all entries that share the same minimal time in one inner loop, the implementation reduces the number of heap operations compared with processing each entry individually. This batch extraction also minimizes the overhead of repeatedly checking the heap’s top element.

Storing the adjacency list as a defaultdict(list) provides O(1) average-case insertion and iteration over neighbors, which is essential for dense graphs where each node may have many incident edges. The seen set offers O(1) membership tests, allowing the algorithm to quickly discard any neighbor that has already been finalized, thereby preventing unnecessary heap insertions and redundant work.

The modulo reduction is performed only when a node is about to be returned or when its ways are propagated to neighbors, avoiding repeated large-integer arithmetic throughout the main loop. This selective reduction contributes to faster execution, especially when the number of distinct paths grows exponentially.

Overall, the combination of a priority queue, batch processing of equal-time entries, and early pruning via the seen set yields an efficient traversal that focuses computation on the truly relevant portion of the search space-the frontier of shortest-time routes.

Imagine a big map with many cities connected by roads, where each road takes a specific amount of time to travel across. The goal is to find how many different ways there are to reach the very last city in the shortest amount of time possible.

To do this, the computer first creates a map of all the roads so it knows which cities are connected to each other. It uses a special list to keep track of all the paths that are currently being explored, always picking the one that arrives at a city the fastest.

As the computer moves along, it keeps a list of cities that it has already finished exploring. This is important because once a city has been reached in the quickest time, visiting it again would only make the trip take longer, so it ignores those extra paths.

When it reaches a city, it groups together all the ways that arrive at the same time. It adds those ways up and continues moving to the next set of cities. This keeps happening until the very last city is reached. Because the number of ways can get very, very large, the computer keeps the number tidy by using a big math rule to keep it manageable. Finally, when it arrives at the last city, the number of ways to get there is ready to be shared.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python				TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python			Go	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	Dijkstra-Edu			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	Shamik07					Dart
	suxrobGM						C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
Dijkstra-Edu	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality