Reconstruct Itinerary I
You are given flight tickets as [from, to] pairs and a starting airport. Every ticket must be used exactly once. Reconstruct the full itinerary; if several are valid, return the lexicographically smallest one as a list of airports.
tickets = [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]], start = "JFK" => ["JFK", "MUC", "LHR", "SFO", "SJC"] tickets = [["JFK","SFO"], ["JFK","ATL"], ["SFO","ATL"], ["ATL","JFK"], ["ATL","SFO"]], start = "JFK" => ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]
Up to 300 tickets; airport codes are three uppercase letters. The tickets always form at least one valid itinerary from start.
Hints
Hint 1
Greedy DFS taking the smallest unused destination. When an airport has no unused tickets left, it must be the END of the route — append it and backtrack. Reverse at the end (Hierholzer's algorithm).
Hint 2
Store each adjacency list in reverse-sorted order so pop() hands you the smallest destination in O(1).