Reconstruct Itinerary

January 10, 2025

Reconstruct Itinerary – Reconstruct Flight Path Problem

You are given a list of flight tickets, where each ticket is represented as tickets [i] = [from_i, to_i]. Here, from_i and to_i are three-letter codes for the source and destination airports.

Your task is to reconstruct the complete flight itinerary in order and return it.

All tickets start from the “JFK” airport.
Each ticket is used exactly once.
If there are multiple valid itineraries, return the one that comes first in lexicographical order.

Illustration: ["JFK", "SEA"] comes before ["JFK", "SFO"].

Examples related to Reconstruct Itinerary - Reconstruct Flight Path Problem

Example 1:

Illustration 1: Input: tickets = [["BUF","HOU"],["HOU","SEA"],["JFK","BUF"]]
Output: ["JFK","BUF","HOU","SEA"]

Example 2:

Illustration 2: Input: tickets = [["HOU","JFK"],["SEA","JFK"],["JFK","SEA"],["JFK","HOU"]]
Output: ["JFK","HOU","JFK","SEA","JFK"]
Explanation: Another possible reconstruction is ["JFK","SEA","JFK","HOU","JFK"] but it is lexicographically larger.

Constraints:

1 <= tickets.length <= 300
from_i != to_i

Hints to solve Reconstruct Flight Path Problem

Hint 1:

Think of this problem as a graph where airports are the nodes and tickets are the edges.
Since you need to use all the tickets exactly once, can you figure out a way to visit every edge of the graph?
Also, how can you make sure the flight path follows the smallest alphabetical order?

Hint 2:

We can create an adjacency list from the tickets to represent the graph. Then, we use DFS to build the itinerary.
To ensure the smallest alphabetical order, we sort the list of destinations for each airport.
Sorting ensures that during DFS, we visit the airport with the smallest name first.

Hint 3:

Simple DFS might not be efficient since it can take O(E * V) time, where E is the number of tickets and V is the number of airports.
Naive approach would involve removing a ticket, exploring, and then adding it back if needed.
Can you think of a better approach? Maybe a modified version of DFS could help.

Hint 4:

You can use Hierholzer’s algorithm, a technique for finding Eulerian paths.
In this approach, instead of adding airports to the result immediately, you visit all its neighbors first (post-order traversal).
Once all DFS calls are done, you reverse the collected path to get the correct itinerary.

Methods to Solve Reconstruct Itinerary - Reconstruct Flight Path Problem

There are mainly 3 approach to solve Reconstruct Flight Path Problem problem:

Depth First Search Method
Hierholzer’s Algorithm (Recursion)
Hierholzer’s Algorithm (Iteration)

1. Depth First Search Method

This method involves performing a depth-first traversal of the graph to build the flight path.
Starting from the given departure point, you recursively explore each destination, marking routes as you go to reconstruct the path in the correct order.
Time complexity: O(E x V)
Space complexity: O(E x V)

Where E is the number of tickets (edges) and V is the number of airports (vertices).

Code:

C++

Java

Python

JavaScript

C++

class Solution {
public:
    vector findItinerary(vector>& tickets) {
        unordered_map> adj;
        for (auto& ticket : tickets) {
            adj[ticket[0]];
        }

        sort(tickets.begin(), tickets.end());
        for (auto& ticket : tickets) {
            adj[ticket[0]].push_back(ticket[1]);
        }

        vector res = {"JFK"};
        dfs("JFK", res, adj, tickets.size() + 1);
        return res;
    }

private:
    bool dfs(const string& src, vector& res, 
             unordered_map>& adj, int targetLen) {
        if (res.size() == targetLen) {
            return true;
        }

        if (adj.find(src) == adj.end()) {
            return false;
        }

        vector temp = adj[src];
        for (int i = 0; i < temp.size(); ++i) {
            string v = temp[i];
            adj[src].erase(adj[src].begin() + i);
            res.push_back(v);
            if (dfs(v, res, adj, targetLen)) return true;
            adj[src].insert(adj[src].begin() + i, v);
            res.pop_back();
        }
        return false;
    }
};

Java

public class Solution {
    public List findItinerary(List> tickets) {
        Map> adj = new HashMap<>();
        for (List ticket : tickets) {
            adj.putIfAbsent(ticket.get(0), new ArrayList<>());
        }
        
        tickets.sort((a, b) -> a.get(1).compareTo(b.get(1)));
        for (List ticket : tickets) {
            adj.get(ticket.get(0)).add(ticket.get(1));
        }
        
        List res = new ArrayList<>();
        res.add("JFK");
        
        if (dfs("JFK", res, adj, tickets.size() + 1)) {
            return res;
        }
        return new ArrayList<>();
    }
    
    private boolean dfs(String src, List res, 
                        Map> adj, int targetLen) {
        if (res.size() == targetLen) {
            return true;
        }
        
        if (!adj.containsKey(src)) {
            return false;
        }
        
        List temp = new ArrayList<>(adj.get(src));
        for (int i = 0; i < temp.size(); i++) {
            String v = temp.get(i);
            adj.get(src).remove(i);
            res.add(v);
            if (dfs(v, res, adj, targetLen)) return true;
            adj.get(src).add(i, v);
            res.remove(res.size() - 1);
        }
        return false;
    }
}

Python

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        adj = {src: [] for src, dst in tickets}
        tickets.sort()
        for src, dst in tickets:
            adj[src].append(dst)

        res = ["JFK"]
        def dfs(src):
            if len(res) == len(tickets) + 1:
                return True
            if src not in adj:
                return False

            temp = list(adj[src])
            for i, v in enumerate(temp):
                adj[src].pop(i)
                res.append(v)
                if dfs(v): return True
                adj[src].insert(i, v)
                res.pop()
            return False
            
        dfs("JFK")
        return res

JavaScript

class Solution {
    /**
     * @param {string[][]} tickets
     * @return {string[]}
     */
    findItinerary(tickets) {
        const adj = {};
        for (const [src, dst] of tickets) {
            if (!adj[src]) adj[src] = [];
        }

        tickets.sort();
        for (const [src, dst] of tickets) {
            adj[src].push(dst);
        }

        const res = ["JFK"];
        const dfs = (src) => {
            if (res.length === tickets.length + 1) return true;
            if (!adj[src]) return false;

            const temp = [...adj[src]];
            for (let i = 0; i < temp.length; i++) {
                const v = temp[i];
                adj[src].splice(i, 1);
                res.push(v);
                if (dfs(v)) return true;
                res.pop();
                adj[src].splice(i, 0, v);
            }
            return false;
        }

        dfs("JFK");
        return res;
    }
}

2. Hierholzer’s Algorithm (Recursion) Method

This approach is used to find Eulerian paths or circuits. It recursively traverses the graph to ensure that all edges are covered exactly once, building the path as it backtracks from dead ends to construct the flight itinerary.
Time complexity: O(E log E)
Space complexity: O(E)

Where E is the number of tickets (edges) and V is the number of airports (vertices).

Code:

C++

Java

Python

JavaScript

C++

class Solution {
public:
    vector findItinerary(vector>& tickets) {
        unordered_map> adj;
        for (auto& ticket : tickets) {
            adj[ticket[0]].push_back(ticket[1]);
        }
        for (auto& [src, dests] : adj) {
            sort(dests.rbegin(), dests.rend());
        }
        
        vector res;
        dfs("JFK", adj, res);
        reverse(res.begin(), res.end());
        return res;
    }

private:
    void dfs(const string& src, unordered_map>& adj, vector& res) {
        while (!adj[src].empty()) {
            string dst = adj[src].back();
            adj[src].pop_back();
            dfs(dst, adj, res);
        }
        res.push_back(src);
    }
};

Java

public class Solution {
    public List findItinerary(List> tickets) {
        Map> adj = new HashMap<>();
        for (List ticket : tickets) {
            String src = ticket.get(0);
            String dst = ticket.get(1);
            adj.computeIfAbsent(src, k -> new PriorityQueue<>()).offer(dst);
        }

        List res = new ArrayList<>();
        dfs(adj, "JFK", res);

        Collections.reverse(res);
        return res;
    }

    private void dfs(Map> adj,
                     String src, List res) {
        PriorityQueue queue = adj.get(src);
        while (queue != null && !queue.isEmpty()) {
            String dst = queue.poll();
            dfs(adj, dst, res);
        }
        res.add(src);
    }
}

Python

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        adj = defaultdict(list)
        for src, dst in sorted(tickets)[::-1]:
            adj[src].append(dst)

        res = []
        def dfs(src):
            while adj[src]:
                dst = adj[src].pop()
                dfs(dst)
            res.append(src)
            
        dfs('JFK')
        return res[::-1]

JavaScript

class Solution {
    /**
     * @param {string[][]} tickets
     * @return {string[]}
     */
    findItinerary(tickets) {
        const adj = new Map();
        const res = [];
        
        tickets.sort().reverse().forEach(([src, dst]) => {
            if (!adj.has(src)) adj.set(src, []);
            adj.get(src).push(dst);
        });
        
        function dfs(src) {
            while (adj.has(src) && adj.get(src).length > 0) {
                const dst = adj.get(src).pop();
                dfs(dst);
            }
            res.push(src);
        }
        
        dfs("JFK");
        return res.reverse();
    }
}

3. Hierholzer’s Algorithm (Iteration) Method

Build a table to solve the problem iteratively, starting from smaller subproblems and combining results. It systematically tracks valid states for substrings, ensuring efficient validation.
Time complexity: O(E log E)
Space complexity: O(E)

Where E is the number of tickets (edges) and V is the number of airports (vertices).

Code:

C++

Java

Python

JavaScript

C++

class Solution {
public:
    vector findItinerary(vector>& tickets) {
        unordered_map> adj;
        for (const auto& ticket : tickets) {
            adj[ticket[0]].push_back(ticket[1]);
        }
        for (auto& [src, destinations] : adj) {
            sort(destinations.rbegin(), destinations.rend());
        }
        
        vector res;
        stack stk;
        stk.push("JFK");
        
        while (!stk.empty()) {
            string curr = stk.top();
            if (adj[curr].empty()) {
                res.push_back(curr);
                stk.pop();
            } else {
                string next = adj[curr].back();
                adj[curr].pop_back();
                stk.push(next);
            }
        }
        
        reverse(res.begin(), res.end());
        return res;
    }
};

Java

public class Solution {
    public List findItinerary(List> tickets) {
        Map> adj = new HashMap<>();
        for (List ticket : tickets) {
            adj.computeIfAbsent(ticket.get(0), 
            k -> new PriorityQueue<>()).add(ticket.get(1));
        }
        
        LinkedList res = new LinkedList<>();
        Stack stack = new Stack<>();
        stack.push("JFK");
        
        while (!stack.isEmpty()) {
            String curr = stack.peek();
            if (!adj.containsKey(curr) || adj.get(curr).isEmpty()) {
                res.addFirst(stack.pop());
            } else {
                stack.push(adj.get(curr).poll());
            }
        }
        
        return res;
    }
}

Python

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        adj = defaultdict(list)
        for src, dst in sorted(tickets)[::-1]:
            adj[src].append(dst)
            
        stack = ["JFK"]
        res = []
        
        while stack:
            curr = stack[-1]
            if not adj[curr]:
                res.append(stack.pop())
            else:
                stack.append(adj[curr].pop())
                
        return res[::-1]

JavaScript

class Solution {
    /**
     * @param {string[][]} tickets
     * @return {string[]}
     */
    findItinerary(tickets) {
        const adj = new Map();
        tickets.sort().reverse().forEach(([src, dst]) => {
            if (!adj.has(src)) adj.set(src, []);
            adj.get(src).push(dst);
        });
        
        const res = [];
        const stack = ["JFK"];
        
        while (stack.length > 0) {
            let curr = stack[stack.length - 1];
            if (!adj.has(curr) || adj.get(curr).length === 0) {
                res.unshift(stack.pop());
            } else {
                stack.push(adj.get(curr).pop());
            }
        }
        
        return res;
    }
}

Unlock this article for Free,
by logging in

Reconstruct Itinerary