Reconstruct Itinerary - Hard Python Advanced Graphs Interview Problem

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets must be used exactly once. The itinerary must begin with "JFK". If there are multiple valid itineraries, return the one that has the smallest lexicographic order when read as a whole.

Example 1

JFK -> MUC -> LHR -> SFO -> SJC

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Explanation: Starting from JFK, the only valid itinerary uses all 4 tickets in the order shown.

Example 2

JFK --> SFO --> ATL --.
 ^               |    |
 |      ATL <---'    ATL
 |       |
 '-- SFO <-- ATL

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: ["JFK","SFO","ATL","JFK","ATL","SFO"] is also valid but lexicographically larger.

Constraints

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters
fromi != toi
The input is guaranteed to have a valid itinerary using all tickets

Hints