algorythms
Graph BFS / DFS
LC #332Hard

Reconstruct Itinerary

Graph BFS / DFS
GoogleAmazonMeta

Problem

Given a list of airline tickets [from, to], reconstruct the itinerary starting from "JFK". Use all tickets exactly once. If multiple valid itineraries exist, return the lexicographically smallest one.

graphdfseulerian-path

Constraints

  • ›1 ≤ tickets.length ≤ 300
  • ›tickets[i].length == 2
  • ›From and to are 3-letter IATA codes
  • ›Guaranteed at least one valid itinerary exists

Example

Inputtickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output["JFK","MUC","LHR","SFO","SJC"]
Why

Start from JFK, follow Eulerian path using all tickets exactly once

Hints — reveal one at a time