Practice/Netflix/Reconstruct Itinerary

Reconstruct Itinerary

CodingMust

Problem Overview

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

All of the tickets belong to a person who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Important Notes

• This is a classic Eulerian path problem in graph theory
• The itinerary must start from "JFK"
• All tickets must be used exactly once
• When multiple valid paths exist, return the lexicographically smallest one
• This problem appears frequently in Netflix interviews

Problem Requirements

Given a list of flight tickets, construct the complete itinerary starting from JFK.

Example 1

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

result = find_itinerary(tickets)

Returns ["JFK","MUC","LHR","SFO","SJC"]

`

Example 2

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

result = find_itinerary(tickets)

Returns ["JFK","ATL","JFK","SFO","ATL","SFO"]

Explanation:

The itinerary ["JFK","ATL","JFK","SFO","ATL","SFO"] has a smaller

lexical order than ["JFK","SFO","ATL","JFK","ATL","SFO"]

`

Requirements

• Build a directed graph from the tickets
• Find an Eulerian path (path that uses every edge exactly once)
• Among multiple valid paths, return the lexicographically smallest one
• Handle cycles and dead ends with backtracking

Clarification Questions to Ask

• Can there be duplicate tickets (same from and to airports)?
• Is the graph guaranteed to have a valid Eulerian path?
• What's the maximum number of tickets?
• Are all airport codes exactly 3 uppercase letters?

Constraints

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• from_i.length == 3
• to_i.length == 3
• from_i and to_i consist of uppercase English letters
• from_i != to_i