Reconstruct Itinerary

LeetCode 332 | Difficulty: Hard

Hard

Problem Description

You are given a list of airline tickets where tickets[i] = [from~i~, to~i~] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

- For example, the itinerary `["JFK", "LGA"]` has a smaller lexical order than `["JFK", "LGB"]`.

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

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

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

Constraints:

- `1 <= tickets.length <= 300`

- `tickets[i].length == 2`

- `from~i~.length == 3`

- `to~i~.length == 3`

- `from~i~` and `to~i~` consist of uppercase English letters.

- `from~i~ != to~i~`

Topics: Array, String, Depth-First Search, Graph Theory, Sorting, Heap (Priority Queue), Eulerian Circuit

---

Approach

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 156 ms)

Metric	Value
Runtime	156 ms
Memory	47.5 MB
Date	2021-12-05

Solution

public class Solution {
    

    public IList<string> FindItinerary(IList<IList<string>> tickets)
    {
        Dictionary<string, List<string>> targets = new Dictionary<string, List<string>>();
    foreach (var ticket in tickets)
    {
        var source = ticket[0];
        var dest = ticket[1];
        if(!targets.ContainsKey(source))
        {
            targets.Add(source, new List<string>() {dest});
        }
        else
        {
            targets[source].Add(dest);
        }
    }
    foreach (var target in targets)
    {
        target.Value.Sort();
    }
    
    LinkedList<string> result = new LinkedList<string>();
    Stack<string> s = new Stack<string>();
    
    s.Push("JFK");
    while(s.Any() )
    {
        while(targets.ContainsKey(s.Peek()) && targets[s.Peek()].Any())
        {
            var next = targets[s.Peek()].First();
            targets[s.Peek()].RemoveAt(0);
            s.Push(next);           
        }
        result.AddFirst(s.Pop());
    }
    return result.ToList();
    }
}

📜 1 more C# submission(s)

Submission (2021-12-05) — 164 ms, 47.3 MB

public class Solution {
    Dictionary<string, List<string>> flightMap = new Dictionary<string, List<string>>();
    LinkedList<string> result = new LinkedList<string>();

    public IList<string> FindItinerary(IList<IList<string>> tickets)
    {
        foreach (var ticket in tickets)
        {
            var origin = ticket[0];
            var dest = ticket[1];
            if (this.flightMap.ContainsKey(origin))
            {
                this.flightMap[origin].Add(dest);
            }
            else
            {
                List<string> destList = new List<string>();
                destList.Add(dest);
                flightMap.Add(origin, destList);

            }
        }

        foreach (var dest in flightMap)
        {
            dest.Value.Sort();
        }
        DfsItinerary("JFK");
        return result.ToList();
    }

    protected void DfsItinerary(string origin)
    {
        if (this.flightMap.ContainsKey(origin))
        {
            var destList = this.flightMap[origin];

            while (destList.Count != 0)
            {
                string dest = destList[0];
                destList.RemoveAt(0);
                DfsItinerary(dest);
            }
        }
        result.AddFirst(origin);
    }
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.