The O(n) Club: Reconstruct Itinerary (JFK Edition): When Your DFS Hits Turbulence

The O(n) Club: Reconstruct Itinerary (JFK Edition): When Your DFS Hits Turbulence

⚡ TL;DR

Given a suitcase full of flight tickets, your mission (should you choose to accept it) is to build a trip starting at “JFK”, using every ticket once, and making sure at every junction, you choose the airport that comes first alphabetically. You want the itinerary, but DFS gives it to you backwards (of course it does). Here’s what NOT to do:

// Wrong but fun: Brute force every path (don’t even...)
// Here’s the right (oversimplified) shape:
List<String> itinerary = new ArrayList<>();
void dfs(String airport, Map<String, List<String>> adj) {
    while (!adj.get(airport).isEmpty()) {
        dfs(adj.get(airport).remove(0), adj);
    }
    itinerary.add(0, airport); // Surprise! Reverse order
}

🧠 How Devs Usually Mess This Up

Let’s get real about classic dev detours:

• Shortest Path Confusion: This isn’t Dijkstra’s Greatest Layovers. There’s no cost, no minimum stops, just pure, uncontaminated lexicography.
• “Hey I’ll just grab the next alphabetical one!” – Sure, but only if you already sorted all possible flights from every airport. Otherwise, you’re playing Russian roulette with a PriorityQueue.
• Order Meltdown: DFS hands you the trip in post-order (backwards), so if you forget to reverse, you’ll watch your traveler circle JFK forever, like a bug lost in an infinite loop.
• Dupe Disasters: If there are two identical (src, dst) tickets, you MUST treat them like unique boarding passes, or you’ll clone someone’s luggage. No bueno.

🔍 What’s Actually Going On

Think of each ticket as a conveyor belt between airports. You need to link every belt without missing one and always pick the alphabetically earliest if there’s a choice. We’re riffing off Hierholzer’s Algorithm—a tool designed for Eulerian Paths, now jazzed up with ‘dictionary police’ making sure ATL always beats ZUR.

Strategy?

• Turn the ticket list into an adjacency map: airport ➡️ all flights out, sorted. (PriorityQueues do the dirty work.)
• DFS from “JFK”, picking the smallest destination each time. When you run out of options at an airport, only then stick it in your itinerary. (Post-order magic!)
• Collect everything backwards, then flip it into forward gear at the end—or just build it from the front as you backtrack.

🛠️ PseudoCode

• Input: List> of tickets
• For each ticket, add it to a map—key: source, value: min-heap of destinations
  

  Map<String, PriorityQueue<String>> adj = new HashMap<>();
  for (List<String> ticket : tickets)
      adj.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));

• Create an empty LinkedList for the route (we’ll add from the head)
• DFS function: as long as the current airport has options, keep recursing into the smallest. After exhausting, add current airport at the start of route.
  

  void dfs(String airport) {
      while (adj.get(airport) != null && !adj.get(airport).isEmpty())
          dfs(adj.get(airport).poll());
      route.addFirst(airport);
  }

• Start at “JFK”, let DFS work, and return route

💻 The Code

import java.util.*;
 public class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> adj = new HashMap<>();
        for (List<String> ticket : tickets) {
            adj.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
        }
        LinkedList<String> route = new LinkedList<>();
        dfs("JFK", adj, route);
        return route;
    }
     private void dfs(String airport, Map<String, PriorityQueue<String>> adj, LinkedList<String> route) {
        PriorityQueue<String> nexts = adj.get(airport);
        while (nexts != null && !nexts.isEmpty()) {
            dfs(nexts.poll(), adj, route);
        }
        route.addFirst(airport);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicate tickets: Every ticket is sacred. Use a PriorityQueue for each airport and remove tickets as you go, so you don’t double-book.
• Forgetting the Reversal: The only thing worse than a missed connection is printing your trip in the wrong order. Insert airports at the front or reverse at the end (and don’t blame the airline).
• Cycles/Stack Overflows: If a test gives you a million tickets, recursion might turn into a stack crash—interviewers love seeing the iterative DFS variant.
• Space/Time Reality: O(E log D) (E = ticket count, D = avg. flights per airport) for building and traversing. Not just O(N), unless you want eye rolls.

🧠 Interviewer Brain-Tattoo

“If you forget to reverse DFS, you’ve coded a magical airline: every traveler starts at their destination and ends up always back at JFK. The dream—of a luggage carousel with only arrivals.”