Reconstruct Itinerary

HardAdvanced Graphs

Use every directed flight ticket exactly once to form an itinerary starting at JFK. Among valid itineraries choose the lexicographically smallest airport sequence.

Example 1

Directed tickets: departure → arrival. Parallel tickets remain separate edges.

tickets = [["JFK","BBB"],["JFK","AAA"],["AAA","JFK"]]

["JFK","AAA","JFK","BBB"]

Explanation

AAA first permits returning to JFK and taking BBB last; BBB first strands unused tickets.

Example 2

Directed tickets: departure → arrival. Parallel tickets remain separate edges.

tickets = [["JFK","AAA"],["AAA","JFK"],["JFK","AAA"]]

["JFK","AAA","JFK","AAA"]

Explanation

Duplicate JFK->AAA tickets are separate edges and each is used.

Example 3

Directed tickets: departure → arrival. Parallel tickets remain separate edges.

tickets = [["JFK","LAX"]]

["JFK","LAX"]

Explanation

The sole ticket gives the only itinerary.

Constraints

1 <= number of tickets <= 300
Airport codes are three uppercase letters
A valid itinerary exists
Duplicate tickets are distinct usable edges

Function contractfindItineraryArguments: json

SolutionRuns on your device

Loading draft…

Reconstruct Itinerary

Example 1

Diagram text alternative

Explanation

Example 2

Diagram text alternative

Explanation

Example 3

Diagram text alternative

Explanation

Constraints

Expected complexity