Reconstruct Itinerary

Understand and solve the interview question "Reconstruct Itinerary".

Description

Assume we have an array of airline tickets represented as pairs of departure and arrival airports like [from, to]. We have to reconstruct the itinerary in order. All tickets belong to a man who departs from a specified location, e.g., JFK. Therefore, the itinerary must begin with JFK. There might be multiple valid itineraries; you must return the itinerary with the smallest lexical order.

Constraints

Consider the following constraints:

  • 1 <= tickets.length <= 300
  • tickets[i].length must be 2.
  • fromi.lengthfrom_i.length, toi.lengthto_i.length == 3
  • fromifrom_i and toito_i consist of uppercase English letters.
  • Specified departure must be the start point of itinerary.
  • fromifrom_i and toito_i would not be equal.
  • Must use all the tickets but only once.

Let’s try to understand the problem with the help of an example:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.