Reconstruct Itinerary
Hard · Graphs · about 30 minutes
Asked at Google, Uber, Pinterest, Meta, Amazon, Airbnb, Zillow, Duolingo, Yelp.
tickets[i] = [from, to] is a one-way flight. All tickets belong to one traveller who started at "JFK". Reconstruct the itinerary that uses every ticket exactly once. If several itineraries are valid, return the one that is smallest in lexical order when read as a single sequence of airports. At least one valid itinerary exists.