332. Reconstruct Itinerary

Given airline tickets [from, to], reconstruct the itinerary in order, starting at JFK and using every ticket exactly once. If several itineraries exist, return the lexically smallest.

The itinerary is an Eulerian path. Greedily follow the smallest unused ticket; when an airport has no tickets left, add it to the route. The route comes out reversed, and dead-end detours are naturally placed at the end.

1function findItinerary(tickets: string[][]): string[] {
2  const adj = new Map<string, string[]>();
3  for (const [a, b] of [...tickets].sort().reverse()) (adj.get(a) ?? adj.set(a, []).get(a)!).push(b);
4  const route: string[] = [];
5  const visit = (a: string) => {
6    const dests = adj.get(a) ?? [];
7    while (dests.length) visit(dests.pop()!);
8    route.push(a);
9  };
10  visit("JFK");
11  return route.reverse();
12}

flights

unused tickets

SFOATL

JFKATL, SFO

ATLJFK, SFO

route (reversed)

empty

Group tickets by departure.

1 / 0

Space: play/pause · ←/→: step