#93 Hard Time O(E log E) Space O(E) Animated

Reconstruct Itinerary

Reconstruct itinerary in lexical order using Eulerian path.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Weighted graph relaxation

Improve a node’s known cost only when a newly discovered path is genuinely better.

Approach: DFS (Eulerian Path)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Improve a node’s known cost only when a newly discovered path is genuinely better.

Common Pitfall

Discard stale priority-queue entries instead of expanding them a second time.

Description

Reconstruct itinerary in lexical order using Eulerian path.

Constraints

Time Complexity: O(E log E)
Space Complexity: O(E)

Solution — DFS (Eulerian Path)

TimeO(E log E) SpaceO(E)

Implementation Plan

Translate the invariant into these small, testable moves.

Initialize distances and a frontier.
Take the cheapest candidate.
Relax each outgoing edge.
Repeat until the target or all reachable nodes are settled.

def findItinerary(tickets):
    adj = collections.defaultdict(list)
    for src, dst in sorted(tickets)[::-1]:
        adj[src].append(dst)
        
    res = []
    def dfs(src):
        while adj[src]:
            dfs(adj[src].pop())
        res.append(src)
        
    dfs("JFK")
    return res[::-1]

Min Cost to Connect All Points

Reconstruct Itinerary

Steps

Description

Constraints

Tags

Solution — DFS (Eulerian Path)