LeetCode 332: Reconstruct Itinerary Solution

Master LeetCode problem 332 (Reconstruct Itinerary), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

332. Reconstruct Itinerary

Hard

Depth-First Search Graph Eulerian Circuit

Problem Explanation

Explanation:

To reconstruct the itinerary, we can use a depth-first search (DFS) algorithm. We will start from the "JFK" airport and explore all possible flights until we use all the tickets. We will keep track of the visited airports and use a priority queue to ensure that we visit the airports in lexical order. At each step, we will choose the smallest lexical order airport as the next airport to visit.

Algorithm:

Create a HashMap to store the list of destinations for each airport.
Sort the destinations list in reverse order to get the smallest lexical order.
Start the DFS from "JFK" and recursively visit all destinations.
Append the airport to the itinerary while backtracking.
Return the reversed itinerary as the final result.

Time Complexity:

The time complexity of this algorithm is O(E * log(E)), where E is the number of edges (flights) in the input.

Space Complexity:

The space complexity is O(E) for storing the flights in the HashMap.

Solution Code

class Solution {
    Map<String, PriorityQueue<String>> flights;
    List<String> itinerary;

    public List<String> findItinerary(List<List<String>> tickets) {
        flights = new HashMap<>();
        itinerary = new LinkedList<>();

        for (List<String> ticket : tickets) {
            flights.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            flights.get(ticket.get(0)).add(ticket.get(1));
        }

        dfs("JFK");
        return itinerary;
    }

    private void dfs(String airport) {
        PriorityQueue<String> destinations = flights.get(airport);
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll());
        }
        itinerary.add(0, airport);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 332 (Reconstruct Itinerary)?

This page provides optimized solutions for LeetCode problem 332 (Reconstruct Itinerary) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 332 (Reconstruct Itinerary)?

The time complexity for LeetCode 332 (Reconstruct Itinerary) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 332 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 332 in Java, C++, or Python.

Back to LeetCode Solutions