Abstract / Summary

Find the second shortest time needed to reach a destination from a start point when moving through a grid.

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 62% (100k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Graph Theory
• Shortest Path

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 solves the problem of finding the second-shortest travel time from node 1 to node n in an undirected graph where each edge takes a fixed travel duration (time) and traffic lights at every node alternate between green and red with a period defined by change. The algorithm builds the adjacency structure, then performs a best-first search that records up to two earliest arrival timestamps for each vertex. When the destination node receives its second distinct timestamp, that value is returned as the answer.

Graph Construction

The first logical block creates an adjacency list using a defaultdict of lists. For each undirected edge [u, v] the code appends the opposite endpoint to both u and v’s neighbor list. This representation enables constant-time iteration over a node’s incident edges during the search phase.

next = defaultdict(list)
for u, v in edges:
    next[u].append(v)
    next[v].append(u)

State Tracking

A second defaultdict called best stores, for each node, a list of the distinct arrival times that have been discovered so far. The algorithm limits this list to at most two entries, reflecting the requirement to keep only the fastest and the second-fastest times.

best = defaultdict(list)

Priority Queue Initialization

The search begins with a priority queue (todo) that holds tuples of the form (current_time, node). The initial entry represents being at the source node 1 at time 0. The use of a heap ensures that the next state to expand always has the smallest recorded time, which is essential for correctly ordering the discovery of earliest arrival timestamps.

todo = [(0, 1)]   # time, node

Main Exploration Loop

The core of the algorithm is a while loop that extracts the smallest-time entry from the heap. The extracted when value denotes the moment the traveler arrives at node. The next step computes the time after traversing one edge (arrive) and incorporates any waiting required by the traffic-light schedule.

while todo:
    when, node = heappop(todo)

    arrive = when + time

    phase, elapsed = divmod(when, change)
    if phase & 1:                     # odd phase = red
        arrive += change - elapsed    # wait for green

Traffic-Light Waiting Logic

The divmod call splits the current time into complete cycles (phase) and the offset within the current cycle (elapsed). The condition phase & 1 checks whether the traveler arrived during a red interval (odd phase). If so, the code adds the remaining time of the red interval (change - elapsed) to arrive, effectively modeling the mandatory wait until the next green period. This handling guarantees that the algorithm respects the alternating signal pattern for every node.

Neighbor Expansion

For each neighbor other of the current node, the algorithm first checks whether the computed arrive timestamp has already been recorded for that neighbor. If it is a duplicate, the neighbor is skipped, preventing redundant work.

for other in next[node]:
    if arrive in best[other]:
        continue

If the neighbor has fewer than two recorded times, the new timestamp is appended. When the neighbor is the destination (n) and this insertion creates the second distinct timestamp, the algorithm terminates immediately, returning the discovered second-shortest travel time.

    if len(best[other]) < 2:
        best[other].append(arrive)

        if other == n and len(best[other]) == 2:
            return arrive

        heappush(todo, (arrive, other))

Edge Cases Handled

The implementation naturally accommodates several subtle scenarios:

• Immediate Arrival at Destination - If the source node is also the destination (n == 1), the first insertion into best[1] occurs with time 0, but the algorithm will only return when a second distinct timestamp is recorded, correctly reflecting the need for a second-shortest path even in a trivial graph.

• Zero-Length Cycles - Because the algorithm records timestamps only when they are distinct, revisiting a node via a zero-cost cycle (hypothetical if time were zero) would not generate duplicate entries, preventing infinite loops.

• Red-Signal Arrival - The waiting logic ensures that arrivals during a red phase are delayed precisely to the start of the next green phase, handling the case where when lands exactly at a phase boundary without extra computation.

• Multiple Paths with Same Travel Time - If two different routes yield the same arrival time at a node, the if arrive in best[other] guard treats them as a single entry, guaranteeing that only distinct timestamps contribute toward the second-shortest measurement.

Performance Optimizations

Several design choices contribute to efficient execution:

• Heap-Based Best-First Search - By always expanding the smallest known time, the algorithm avoids exploring longer paths before shorter ones, reducing the number of heap operations required to reach the second-shortest timestamp.

• Limiting Stored Times per Node - Restricting each node’s best list to two entries eliminates unnecessary memory growth and prevents the search from considering paths that cannot improve the final answer.

• Duplicate Timestamp Pruning - The explicit check for existing timestamps (if arrive in best[other]) stops the algorithm from inserting identical times, which would otherwise cause redundant heap pushes and extra neighbor processing.

• Early Termination on Destination - As soon as the destination node acquires its second distinct arrival time, the function returns, bypassing any further exploration of the graph. This early exit can dramatically cut the number of processed states, especially in dense graphs.

• In-Place Traffic-Light Calculation - The use of divmod and a bitwise test (phase & 1) provides a compact and fast way to decide whether waiting is needed, avoiding more verbose conditional structures.

Overall, the code combines a concise representation of the graph, a disciplined state-keeping strategy, and a priority-queue driven exploration that together deliver a solution tailored to the problem’s constraints while maintaining low overhead in both time and memory usage.

Imagine you are playing a game where you travel between different houses connected by pathways. You want to get to the very last house, but you have to visit it exactly twice to find the second quickest way to arrive.

First, the code makes a map of all the houses and the paths that connect them so it knows where a traveler can go next. It starts at the first house at the beginning of the day.

Since traffic lights are everywhere, the travel time changes depending on whether the light is green or red. The traffic lights switch colors every few minutes. If a traveler gets to a light while it is red, they must wait patiently until it turns green again before moving forward.

The program keeps track of when the traveler arrives at each house. It is looking for two different times to reach every spot. It checks the map, moves to the next house while adding the time it took to travel, and waits for red lights if necessary. Every time a traveler reaches a new house, the program remembers how long it took. By repeating this process, it eventually finds the second shortest time it takes to finally reach the destination house.

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

not analyzed yet

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++		Python	Java		TS
	WalkCCC	C++		Python	Java
	leetcode.ca			Python	Java
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
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