Hard

Quiz

#332 Reconstruct Itinerary

APPROACH

You are given a list of airline tickets where tickets[i] = [fromi, toi] represents one flight. All tickets belong to a traveler departing from "JFK", so the itinerary must begin with "JFK". Every ticket must be used exactly once.

If multiple valid itineraries exist, return the one with the smallest lexical order when read as a single string.

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"]

Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

1 of 4

1:00

What is the optimal approach for this problem?