Route Through Every Boarding Pass

Hard

A traveller has dropped a stack of boarding passes. Each pass passes[i] = [from, to] is one flight from airport from to airport to; airports are written as three-letter codes. The trip started at "JFK", and every pass was flown exactly once. Rebuild the trip: return the list of airports in the order they were visited, starting with "JFK". If several routes fit, return the one that comes first alphabetically when the lists are compared airport by airport from the left (for example, ["JFK", "AMS"] comes before ["JFK", "ATH"]). At least one route using all the passes is guaranteed to exist.

Example 1

passes=[['OSL', 'RIX'], ['JFK', 'DUB'], ['DUB', 'OSL']] → ['JFK', 'DUB', 'OSL', 'RIX']

From JFK the only pass goes to DUB, then on to OSL and finally RIX. There is only one possible route.

Example 2

passes=[['JFK', 'LIS'], ['JFK', 'CPH'], ['CPH', 'JFK'], ['LIS', 'CPH']] → ['JFK', 'CPH', 'JFK', 'LIS', 'CPH']

Two routes work: JFK, CPH, JFK, LIS, CPH and JFK, LIS, CPH, JFK, CPH. The first comes earlier alphabetically, since CPH < LIS at the second stop.

Example 3

passes=[['JFK', 'AMS']] → ['JFK', 'AMS']

Constraints

1 ≤ len(passes) ≤ 300
passes[i] = [from, to], where from and to are exactly 3 uppercase English letters
from ≠ to
A route from "JFK" using every pass exists

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Graph Eulerian Circuit