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

Reconstruct Itinerary

Reconstruct itinerary in lexical order using Eulerian path.

LeetCode ↗

Approach: DFS (Eulerian Path)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Reconstruct itinerary in lexical order using Eulerian path.

Constraints

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

Solution — DFS (Eulerian Path)

O(E log E) O(E)

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)