Reconstruct Itinerary

Problem in Plain English

Given every flight ticket as a directed edge, rebuild the complete trip that starts at 'JFK' and uses each ticket exactly once, choosing the smallest lexical order when several trips work.

Problem Statement

You are given a list of airline tickets where each tickets[i] = [from, to] is one directed flight from airport from to airport to. Reconstruct the full itinerary that starts at airport JFK and uses every ticket exactly once, returning the airports in visiting order.

When several itineraries consume all tickets, return the one that is smallest in lexical order when read as a single string. The input always admits at least one valid itinerary, and duplicate tickets between the same airports may appear.

Constraints

1 <= tickets.length <= 300
tickets[i].length == 2
Each airport code has length 3 and uses uppercase English letters.
Departure and arrival airports of one ticket are never equal.

Examples

Example 1

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

The route ["JFK","SFO","ATL","JFK","ATL","SFO"] also uses every ticket but is larger in lexical order.

Example 2

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

Only one ordering consumes every ticket: JFK to MUC to LHR to SFO to SJC.

Example 3

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

KUL is smaller than NRT but has no departure, so taking it first strands two tickets. The NRT cycle must come before the final JFK to KUL flight.

Example 4

Input: tickets = [["JFK","ATL"]]
Output: ["JFK","ATL"]

One ticket needs two airport entries: the starting JFK and its only destination ATL.

Example 5

Input: tickets = [["JFK","ATL"],["JFK","ATL"],["ATL","JFK"]]
Output: ["JFK","ATL","JFK","ATL"]

The two identical JFK to ATL tickets are separate flights. Returning to JFK between them consumes both copies exactly once.

Intuition

Tickets are directed edges, and repeated airport names are allowed because the restriction is on tickets, not airports. Example 1 must use both departures from JFK and both from ATL. A small next airport is desirable only if the remaining tickets can still be used: with JFK to KUL, JFK to NRT and NRT to JFK, choosing KUL immediately gets stuck. Backtracking tests whether a choice can finish; postorder traversal instead delays each stuck airport until the end of the final itinerary.

Approaches

DFS Backtracking Search

Solution Details

Reveal DFS Backtracking Search: intuition, complexity, and code

Intuition

Start at JFK and always board the smallest unused departure, undoing the walk whenever a dead end strands tickets. Exploring departures in sorted order finds the lexical answer because the first complete walk committed is the smallest one that consumes every ticket.

Step-by-Step Logic

Copy each ticket into an adjacency list and sort each departure list ascending; keep duplicate entries. Example 1 gives ATL: [JFK, SFO], JFK: [ATL, SFO], and SFO: [ATL].
Start the route at [JFK] and board the smallest unused departure, JFK to ATL, giving [JFK, ATL].
From ATL board its smallest unused departure to JFK, giving [JFK, ATL, JFK].
From JFK the only unused departure left goes to SFO, then SFO to ATL, then ATL to SFO, giving [JFK, ATL, JFK, SFO, ATL, SFO].
If a partial route gets stuck, remove its last airport and restore its ticket at the original sorted index before trying the next departure. When the route contains E + 1 airports, return success through every caller. Example 1 reaches 6 airports with no failed branch.

Why It Works

The route always starts at JFK and contains exactly the tickets temporarily removed from the adjacency lists. Trying a departure extends a legal directed walk; restoring it at the same index after failure makes every other choice available in sorted order. Thus every possible complete ticket sequence is considered until one has E + 1 airport entries. At the first airport where two candidate routes differ, the smaller destination is searched fully before the larger one. The first complete route is therefore lexicographically smallest. Duplicate destinations occupy separate list entries, so no ticket copy disappears.

Dry Run

DFS Backtracking Search: variable states at each step
depth	airport	action	unused tickets	route so far
0	JFK	initialize	5	[JFK]
0	JFK	remove JFK to ATL	4	[JFK, ATL]
1	ATL	remove ATL to JFK	3	[JFK, ATL, JFK]
2	JFK	remove JFK to SFO	2	[JFK, ATL, JFK, SFO]
3	SFO	remove SFO to ATL	1	[JFK, ATL, JFK, SFO, ATL]
4	ATL	remove ATL to SFO	0	[JFK, ATL, JFK, SFO, ATL, SFO]
5	SFO	6 airports equals E + 1; success propagates without restoring tickets	0	return [JFK, ATL, JFK, SFO, ATL, SFO]

Complexity Analysis

Time Complexity

O(E!)

Space Complexity

O(V + E)

Let E be the ticket count and V the distinct airport count. The search tree has at most E! complete ticket permutations. At depth d, at most E - d removals/restorations shift at most E - d list entries; summing these costs over all prefixes is O(E!) for E >= 2. Sorting adds O(E log E), which is dominated by that factorial bound. Copied adjacency lists hold E entries and V keys, the route and call stack hold O(E), and sorting workspace fits O(E). Inputs remain unchanged. This teaching approach can be impractical on adversarial 300-ticket branching inputs.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<String> findItinerary(List<List<String>> tickets) {5        Map<String, List<String>> adj = new HashMap<>();6        for (List<String> t : tickets) {7            adj.putIfAbsent(t.get(0), new ArrayList<>());8            adj.get(t.get(0)).add(t.get(1));9        }10        for (List<String> dests : adj.values()) {11            Collections.sort(dests);12        }13        List<String> route = new ArrayList<>();14        route.add("JFK");15        dfs("JFK", adj, route, tickets.size());16        return route;17    }18
19    private boolean dfs(String airport, Map<String, List<String>> adj, List<String> route, int total) {20        if (route.size() == total + 1) {21            return true;22        }23        List<String> dests = adj.get(airport);24        if (dests == null) {25            return false;26        }27        for (int i = 0; i < dests.size(); i++) {28            String next = dests.remove(i);29            route.add(next);30            if (dfs(next, adj, route, total)) {31                return true;32            }33            route.remove(route.size() - 1);34            // Restore this ticket at its sorted position before exploring a sibling.35            dests.add(i, next);36        }37        return false;38    }39}

Hints

Hint 1

Using every ticket once means the route is an Eulerian trail through the flight graph, not a shortest path.

Hint 2

Explore the smallest unused departure first, keeping each airport departures reverse-sorted so pop takes it in

O(1)

time; exploration order alone is not the final route.

Hint 3

Append an airport to the answer after its departures run out, then reverse the answer, because the stuck airport is the trip end.

Edge Cases

Duplicate tickets between the same airports stay correct because each copy is its own stack entry popped exactly once.
Cycles such as ATL to JFK back to ATL resolve naturally since the unwind order places the cycle interior before its entry airport.
Airports with no departures, like the final stop, only ever appear as appends during the unwind.

Common Mistakes and Interview Tips

Greedily locking in the smallest next airport without backtracking strands tickets and returns a route shorter than tickets.length + 1.
Sorting departures ascending and removing from the front repeats linear shifts; reverse-sort and pop from the end instead.
Appending airports on the way down instead of on the unwind keeps lexical order but drops tickets trapped inside cycles.

Key Takeaway

When a graph problem demands using every edge exactly once, think Eulerian trail and build the answer with postorder appends: consume edges on the way down and record vertices on the way back up.