Reconstruct Itinerary

Understand and solve the interview question "Reconstruct Itinerary".

We'll cover the following

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.