Reconstruct Itinerary

Hard · Advanced Graphs

You are given a list of airline tickets, each ticket being a pair of [departure_airport, arrival_airport] codes. Starting from "JFK", reconstruct the full itinerary that uses every ticket exactly once. If multiple valid itineraries exist, return the one that visits airports in the smallest lexical order at each step. It is guaranteed that at least one valid itinerary exists.

Examples

Input:  tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Why:    Only one path uses every ticket exactly once starting from JFK.

Input:  tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Why:    Two routes use all tickets, but choosing ATL before SFO from JFK gives the lexically smaller full path.

Input:  tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
Output: ["JFK","NRT","JFK","KUL"]
Why:    Going to KUL first would strand the traveler since KUL has no outgoing ticket, so NRT must be visited first.

Constraints

1 <= tickets.length <= 300, each ticket is a pair of 3-uppercase-letter airport codes, and at least one valid itinerary using all tickets starting at "JFK" is guaranteed to exist.

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Reconstruct Itinerary

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Reconstruct Itinerary. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.