93.Reconstruct Itinerary

HardGraphs · 14/19

Problem

You are given a list of airline tickets where tickets[i] = [from, to] is a one-way flight. Reconstruct the itinerary in order and return it.

The trip always starts at "JFK" and you must use every ticket exactly once. If several valid itineraries exist, return the one that is smallest in lexical order when read as a single string. The input is guaranteed to admit at least one valid itinerary.

Examples

Input:  tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Explanation: There is only one way to chain all four tickets from JFK.

Input:  tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: ["JFK","SFO","ATL","JFK","ATL","SFO"] is also valid but is lexically larger.

Input:  tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
Output: ["JFK","NRT","JFK","KUL"]
Explanation: Greedily flying to KUL first (smaller name) gets stuck, because KUL has no outgoing ticket.

Constraints

1 <= tickets.length <= 300
tickets[i].length == 2
from.length == 3, to.length == 3, uppercase English letters
from != to
At least one valid itinerary exists.

💡 Key Insight

Using every edge exactly once is an Eulerian path problem. Hierholzer's algorithm builds it in linear time: always take the smallest available outgoing edge, and when an airport has no tickets left, append it to the answer. Airports are therefore finalised in reverse — a dead end (like KUL above) is pushed first and ends up last — so reversing the post-order gives the lexically smallest valid itinerary without any backtracking.

Backtracking DFS

TimeO(E^d) in the worst caseSpaceO(E)

Intuition

Sort each airport's destinations. From JFK, try destinations in alphabetical order, consuming a ticket each time. If we have used all tickets, the current route is the answer (it is the lexically smallest because we tried choices in sorted order). If we get stuck early, undo the last ticket and try the next destination.

Algorithm

Build adj: from -> sorted list of to.
route = ["JFK"]. Call dfs("JFK").
In dfs(airport): if route.size() == tickets.size() + 1 return true.
For each index i in adj[airport]: remove destination dest = list.remove(i), append it to route, recurse; if the recursion succeeds return true; otherwise remove it from route and re-insert it at index i.
Return false.

Visualization

tickets: JFK->KUL, JFK->NRT, NRT->JFK
adj: JFK:[KUL, NRT]  NRT:[JFK]

dfs(JFK) try KUL: route=[JFK,KUL], KUL has no tickets, 1 ticket used of 3 -> fail, undo
         try NRT: route=[JFK,NRT] -> dfs(NRT) try JFK: route=[JFK,NRT,JFK]
                  -> dfs(JFK) try KUL: route=[JFK,NRT,JFK,KUL], size 4 == 3+1 -> success

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

class Solution {
    private final Map<String, List<String>> adj = new HashMap<>();
    private final LinkedList<String> route = new LinkedList<>();
    private int totalTickets;

    public List<String> findItinerary(List<List<String>> tickets) {
        totalTickets = tickets.size();
        for (List<String> t : tickets) {
            adj.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
        }
        for (List<String> dests : adj.values()) {
            Collections.sort(dests); // try lexically smaller destinations first
        }
        route.add("JFK");
        dfs("JFK");
        return route;
    }

    private boolean dfs(String airport) {
        if (route.size() == totalTickets + 1) {
            return true; // every ticket used
        }
        List<String> dests = adj.get(airport);
        if (dests == null) {
            return false;
        }
        for (int i = 0; i < dests.size(); i++) {
            String next = dests.remove(i); // use this ticket
            route.add(next);
            if (dfs(next)) {
                return true;
            }
            route.removeLast(); // backtrack
            dests.add(i, next);
        }
        return false;
    }
}

Complexity

Time: O(E^d) in the worst case — d is the max out-degree; backtracking can explore many partial routes. Sorting adds O(E log E).
Space: O(E) — adjacency lists, route and recursion depth.

Hierholzer's AlgorithmOptimal

TimeO(E log E)SpaceO(E)

Intuition

Keep each airport's destinations in a min-heap. DFS greedily pops the smallest destination and recurses. When an airport has no outgoing tickets left, it can only be the end of whatever remains, so we add it to the front of the result. A dead end reached too early (like KUL) is therefore placed at the end, and the detour (NRT -> JFK) is spliced in before it automatically. Every edge is used exactly once, so no backtracking is ever needed.

Algorithm

Build adj: from -> PriorityQueue<String> of destinations.
dfs(airport): while adj[airport] is non-empty, dfs(adj[airport].poll()). Then addFirst(airport) to the result.
Call dfs("JFK") and return the result.

Dry Run

flowchart LR
    JFK["JFK"] -->|"1st pop: KUL"| KUL["KUL<br/>dead end -> result = [KUL]"]
    JFK -->|"2nd pop: NRT"| NRT["NRT"]
    NRT -->|"pop: JFK"| JFK2["JFK<br/>no tickets left -> [JFK, KUL]"]
    NRT -.->|"NRT finished"| R1["result = [NRT, JFK, KUL]"]
    R1 -.->|"JFK finished"| R2["result = [JFK, NRT, JFK, KUL]"]

call stack                      action
dfs(JFK) pop KUL -> dfs(KUL)    KUL has nothing -> addFirst KUL      [KUL]
dfs(JFK) pop NRT -> dfs(NRT)
  dfs(NRT) pop JFK -> dfs(JFK)  JFK heap empty -> addFirst JFK       [JFK, KUL]
  dfs(NRT) done                 addFirst NRT                          [NRT, JFK, KUL]
dfs(JFK) done                   addFirst JFK                          [JFK, NRT, JFK, KUL]

Code

java

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    private final Map<String, PriorityQueue<String>> adj = new HashMap<>();
    private final LinkedList<String> result = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets) {
            adj.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1));
        }
        dfs("JFK");
        return result;
    }

    private void dfs(String airport) {
        PriorityQueue<String> dests = adj.get(airport);
        while (dests != null && !dests.isEmpty()) {
            dfs(dests.poll()); // consume the smallest remaining ticket
        }
        result.addFirst(airport); // post-order: airport is finished
    }
}

Complexity

Time: O(E log E) — every ticket is pushed and popped from a heap once.
Space: O(E) — heaps, result list and recursion depth up to E.

Complexity Comparison

Approach	Time	Space
Backtracking DFS	Exponential worst case	O(E)
Hierholzer's Algorithm	O(E log E)	O(E)

Common Pitfalls

Pure greedy without backtracking or post-order — it flies to KUL first and gets stuck.
Using a Set for destinations: duplicate tickets (e.g. two JFK -> ATL) are legal and must both be used.
Appending airports in pre-order instead of post-order in Hierholzer's; the result must be built in reverse finishing order.
Forgetting that some airports have no outgoing tickets at all, so adj.get(airport) can be null.