Search⌘ K
Home
Courses
Decode the Coding Interview in Kotlin: Real-World Examples

Reconstruct Itinerary

Explore how to reconstruct an itinerary from flight tickets using a depth-first search algorithm in Kotlin. Learn to create a graph structure, perform lexical sorting, and apply DFS to generate the correct travel route. This lesson helps you understand graph traversal and algorithm optimization for coding interviews.

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
...