 All Problems
Reconstruct Itinerary
hard
topological sort
graph
dfs
eulerian path
amazon
google
facebook
uber

You are given a list of airline tickets where tickets[i] = [from, to]. Reconstruct the itinerary in order starting from "JFK". If multiple valid itineraries exist, return the one with the lexicographically smallest airport order.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

Constraints:

  • 1 <= tickets.length <= 300
  • All airports consist of uppercase letters.
Run to check your code against the sample cases, or submit to run every case