FastPrepReconstruct an Itinerary

Reconstruct an Itinerary

Meta logoMeta● HardFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Each ticket is a directed flight [from, to]. Build an itinerary that begins at JFK and uses every ticket exactly once. Return the airports in travel order, including the starting airport. Tickets with the same endpoints are distinct and must each be used.

At least one complete itinerary is guaranteed. If several complete itineraries exist, return the lexicographically smallest airport sequence. An early alphabetical choice may lead to a dead end, so the returned route must still use every ticket.

Function

findItinerary(tickets: String[][]) → String[]

Examples

Example 1

tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]return = ["JFK","MUC","LHR","SFO","SJC"]

The tickets form one complete route from JFK.

Example 2

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]return = ["JFK","ATL","JFK","SFO","ATL","SFO"]

Both first destinations can be completed, but starting with ATL gives the lexicographically smaller itinerary.

Example 3

tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]return = ["JFK","NRT","JFK","KUL"]

Taking JFK → KUL first gets stuck. The complete route takes the NRT circuit before the final KUL ticket.

Constraints

  • 1 <= tickets.length <= 300
  • Each ticket has exactly two airport codes.
  • Each airport code has exactly three uppercase English letters.
  • The departure and arrival on a ticket differ.
  • A complete itinerary beginning at JFK always exists.

More Meta problems

See Meta hiring insights
public String[] findItinerary(String[][] tickets) {
    // Write your code here
}
tickets[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
expected["JFK", "MUC", "LHR", "SFO", "SJC"]
Checking account…