Replanning the Trip

TIP103 Unit 12 Session 2 (Click for link to problem statements)

Replanning the Trip

You hold a stack of one-way airline tickets as [from, to] pairs in tickets, and every ticket must be used exactly once. All itineraries begin at "JFK".

Return the itinerary that uses all tickets and, among valid options, has the smallest lexical order when read as a single list.

def find_itinerary(tickets):
    pass

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 30-40 mins
• 🛠️ Topics: Graphs, Depth-First Search (DFS), Eulerian Path, Hierholzer's Algorithm, Greedy

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does it mean to use every ticket exactly once?

  • A: Each [from, to] pair is one flight we must take. The itinerary is a sequence of airports where each consecutive pair consumes exactly one unused ticket, and no ticket is left over. This is an Eulerian path: a walk that uses every edge of the graph exactly once.

• Q: What does "smallest lexical order" mean when several valid itineraries exist?

  • A: Reading each itinerary as a single list of airport strings, we return the one that compares smallest. For example, ["JFK", "LGA"] comes before ["JFK", "LGB"], so whenever there is a choice of destination we prefer the alphabetically smaller one — as long as it still lets us use every ticket.

• Q: Can the same airport appear more than once in the itinerary? Can there be duplicate tickets?

  • A: Yes to both. An airport can be visited multiple times if multiple tickets route through it, and the input may contain repeated [from, to] pairs — each copy must be used once.

HAPPY CASE
Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ['JFK', 'MUC', 'LHR', 'SFO', 'SJC']
Explanation: Starting at JFK, the only chain that uses all four tickets is JFK -> MUC -> LHR -> SFO -> SJC.

Input: tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
Output: ['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']
Explanation: Two full itineraries exist, but ['JFK', 'ATL', ...] is lexically smaller than ['JFK', 'SFO', ...], so we take the ATL ticket out of JFK first.

EDGE CASE
Input: tickets = [["JFK", "ATL"]]
Output: ['JFK', 'ATL']
Explanation: A single ticket produces a two-airport itinerary.

Input: tickets = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]
Output: ['JFK', 'NRT', 'JFK', 'KUL']
Explanation: KUL is lexically smaller than NRT, but flying JFK -> KUL first strands us in KUL with the NRT tickets unused. The greedy choice must be abandoned in favor of an itinerary that uses every ticket.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Graph Traversal Problems where every edge must be used exactly once, we can consider the following approaches:

• Eulerian Path via Hierholzer's Algorithm: Model airports as nodes and tickets as directed edges, then walk the graph consuming edges via post-order DFS. The itinerary is the reverse of the post-order.
• Greedy + Min-Heap (Priority Queue): To get the smallest lexical order, always fly to the alphabetically smallest destination still available from the current airport. Storing each airport's destinations in a min-heap makes this choice O(log E).
• Backtracking: A brute-force DFS that tries destinations in sorted order and undoes choices that strand unused tickets also works, but it can revisit states exponentially; Hierholzer's algorithm avoids the backtracking entirely.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Build a directed graph mapping each departure airport to a min-heap of its ticket destinations. Run a DFS from "JFK" that repeatedly pops the smallest available destination and recurses; an airport is appended to the result only after all of its outgoing tickets are exhausted (post-order). Reversing that post-order yields the lexically smallest itinerary that uses every ticket — dead-end airports get buried at the end of the list automatically, so no explicit backtracking is needed.

1) Build a graph: for each ticket [from, to], push `to` onto a min-heap keyed by `from`.
2) Define a DFS helper visit(airport):
   a) While the airport still has unused departing tickets:
      i) Pop the lexically smallest destination from its heap (consuming that ticket).
      ii) Recursively visit that destination.
   b) Once the airport has no tickets left, append it to the itinerary list.
3) Call visit("JFK").
4) Reverse the itinerary list and return it.

⚠️ Common Mistakes

• Greedily flying to the smallest destination and appending airports in pre-order — this strands the traversal at dead ends (see the KUL/NRT edge case) and drops unused tickets.
• Forgetting to remove (consume) a ticket when it is used, causing infinite loops on cyclic routes.
• Using a sorted list and popping from the front with pop(0) inside the loop, or re-sorting per visit, which inflates the runtime.
• Forgetting to reverse the post-order list before returning it.
• Marking airports as "visited" like a standard DFS — nodes may be revisited; it is the edges (tickets) that are used exactly once.

4: I-mplement

Implement the code to solve the algorithm.

from collections import defaultdict
import heapq

def find_itinerary(tickets):
    # Build the graph: each departure airport maps to a min-heap of destinations
    graph = defaultdict(list)
    for departure, destination in tickets:
        heapq.heappush(graph[departure], destination)

    itinerary = []

    def visit(airport):
        # Always fly to the smallest lexical destination still available,
        # consuming that ticket as we go
        while graph[airport]:
            next_stop = heapq.heappop(graph[airport])
            visit(next_stop)
        # Add the airport only after all its outgoing tickets are used (post-order)
        itinerary.append(airport)

    visit("JFK")
    # Reverse the post-order to get the actual flight order
    return itinerary[::-1]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: tickets = "MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"

  • Graph: JFK -> [MUC], MUC -> [LHR], LHR -> [SFO], SFO -> [SJC]
  • visit(JFK) pops MUC; visit(MUC) pops LHR; visit(LHR) pops SFO; visit(SFO) pops SJC; visit(SJC) has no tickets, so SJC is appended first.
  • Post-order fills as [SJC, SFO, LHR, MUC, JFK]; reversed gives the answer.
  • Output: ['JFK', 'MUC', 'LHR', 'SFO', 'SJC']

• Input: tickets = "JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"

  • visit(JFK) pops KUL first (smallest); visit(KUL) has no tickets, so KUL is appended first — the dead end sinks to the back of the list.
  • Back in visit(JFK), NRT is popped; visit(NRT) pops JFK; that inner visit(JFK) has no tickets left and appends JFK, then NRT is appended, then the outer JFK.
  • Post-order is [KUL, JFK, NRT, JFK]; reversed gives the answer.
  • Output: ['JFK', 'NRT', 'JFK', 'KUL']

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume E is the number of tickets (edges) and V is the number of distinct airports (nodes).

• Time Complexity: O(E log E) because each ticket is pushed onto and popped from a heap exactly once, and each heap operation costs O(log E) in the worst case.
• Space Complexity: O(E + V) for the graph's heaps and the itinerary list, plus up to O(E) recursion stack in the worst case (one nested call per consumed ticket).