How should I practice Reconstruct an Itinerary Without a Fixed Start?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Pinterest phone screen problems in FastPrep.

Is Reconstruct an Itinerary Without a Fixed Start associated with Pinterest?

FastPrep tags this as a Pinterest phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Reconstruct an Itinerary Without a Fixed Start

Learn this problem

● Hard

PinterestFULLTIMEPHONE SCREEN

Problem statement

You are given directed flight tickets, where tickets[i] = [from, to]. Use every ticket exactly once and return the airports in travel order.

A valid itinerary is guaranteed to exist. The starting airport is not fixed:

If one airport has exactly one more outgoing ticket than incoming tickets, it is the required start.
Otherwise the tickets form an Eulerian circuit; start at the lexicographically smallest airport that has an outgoing ticket.

When more than one complete itinerary is possible from that start, return the lexicographically smallest airport sequence.

Function

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

Examples

Example 1

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

The tickets form a circuit, so the lexicographically smallest airport with an outgoing ticket, ATL, is used as the start.

Example 2

tickets = [["A","B"],["A","C"],["B","A"]]return = ["A","B","A","C"]

Airport A has one extra outgoing ticket and is the required start. Choosing B before C produces the lexicographically smallest complete path.

Example 3

tickets = [["B","C"],["A","B"]]return = ["A","B","C"]

The degree difference identifies A as the only valid start.

Constraints

1 <= tickets.length <= 2 * 10^5
tickets[i].length == 2
Every airport name has between 1 and 10 uppercase English letters.
The tickets admit at least one itinerary that uses every ticket exactly once.