What is the time complexity of Reconstruct Itinerary?

The optimal solution has a time complexity of O(E).

What data structures are used to solve Reconstruct Itinerary?

This problem uses Depth-First Search, Graph, Eulerian Circuit. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Reconstruct Itinerary?

Insight 1: The problem can be modeled as finding an Eulerian path/circuit in a directed graph, where airports are nodes and tickets are edges. Insight 2: The lexical order constraint requires sorting the destination airports in reverse lexicographical order before traversing the graph using Depth-First Search (DFS). This ensures the algorithm explores the smallest lexical order paths first.

Which companies ask LeetCode 332. Reconstruct Itinerary in interviews?

This problem is frequently asked at Booking.com, Flipkart, Netflix, Pinterest, Snap and 3 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Reconstruct Itinerary - LeetCode 332 Solution

Reconstruct Itinerary - Complete Solution Guide

Reconstruct Itinerary is LeetCode problem 332, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 ord

Detailed Explanation

The problem requires reconstructing a flight itinerary from a given list of tickets. Each ticket represents a flight from one airport to another. The itinerary must start from "JFK", and all tickets must be used exactly once. If multiple valid itineraries exist, the itinerary with the smallest lexical order should be returned. It is guaranteed that at least one valid itinerary exists.

Solution Approach

The provided solution uses a Depth-First Search (DFS) algorithm to traverse the graph of airports and tickets. The algorithm builds an adjacency list representation of the graph where keys are departure airports and values are a list of possible destination airports. The destinations are sorted in reverse lexicographical order. The DFS starts from "JFK", recursively visits unvisited airports based on the ticket information and adds the airports to the itinerary in reverse order of visiting. Finally, the itinerary is reversed to obtain the correct order.

Step-by-Step Algorithm

Step 1: Create a graph (adjacency list) to represent the tickets. The keys are the departure airports, and the values are lists of possible destination airports.
Step 2: Sort the destination airports in reverse lexicographical order for each departure airport. This ensures that when multiple options are available, the algorithm chooses the smallest lexical order airport first.
Step 3: Initialize an empty itinerary list.
Step 4: Implement a recursive DFS function that takes the current airport as input.
Step 5: Inside the DFS function, while there are unvisited destinations from the current airport, pop the last destination airport from the sorted list (due to reverse sorting, popping the last element gives the smallest lexical element). Recursively call DFS on the popped destination airport.
Step 6: After visiting all reachable airports from the current airport, append the current airport to the itinerary list.
Step 7: Start the DFS from "JFK".
Step 8: Reverse the itinerary list to obtain the correct order, as the DFS adds airports in reverse order of traversal.
Step 9: Return the reversed itinerary.

Key Insights

Insight 1: The problem can be modeled as finding an Eulerian path/circuit in a directed graph, where airports are nodes and tickets are edges.
Insight 2: The lexical order constraint requires sorting the destination airports in reverse lexicographical order before traversing the graph using Depth-First Search (DFS). This ensures the algorithm explores the smallest lexical order paths first.
Insight 3: Using a data structure that allows efficient removal of edges (tickets) is crucial for performance. In Python, using `pop()` on a sorted list allows us to remove destinations in the desired order.

Complexity Analysis

Time Complexity: O(E)

Space Complexity: O(E)

Topics

This problem involves: Depth-First Search, Graph, Eulerian Circuit.

Companies

Asked at: Booking.com, Flipkart, Netflix, Pinterest, Snap, Twilio, Yandex, eBay.

Reconstruct Itinerary | LeetCode 332

Hard

Depth-First Search Graph Eulerian Circuit

Time: O(E)Space: O(E)

Solution Code

Available in:

import java.util.*;

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

        for (String src : graph.keySet()) {
            Collections.sort(graph.get(src), Collections.reverseOrder());
        }

        List<String> itinerary = new ArrayList<>();

        function dfs = (airport) -> {
            while (graph.containsKey(airport) && !graph.get(airport).isEmpty()) {
                String next_airport = graph.get(airport).remove(graph.get(airport).size() - 1);
                dfs.apply(next_airport);
            }
            itinerary.add(airport);
        };
        
        interface function {
            void apply(String airport);
        }


        dfs.apply("JFK");

        Collections.reverse(itinerary);
        return itinerary;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 332: Reconstruct Itinerary - Detailed explanation and solution approaches.

Topics

Depth-First Search Graph Eulerian Circuit

Companies

Booking.comFlipkartNetflixPinterestSnapTwilioYandexeBay

Stats

Difficulty:Hard

Languages:4

Companies:8

Problem #:332

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Create a graph (adjacency list) to represent the tickets. The keys are the departure airports, and the values are lists of possible destination airports.
2
Step 2: Sort the destination airports in reverse lexicographical order for each departure airport. This ensures that when multiple options are available, the algorithm chooses the smallest lexical order airport first.
3
Step 3: Initialize an empty itinerary list.
4
Step 4: Implement a recursive DFS function that takes the current airport as input.
5
Step 5: Inside the DFS function, while there are unvisited destinations from the current airport, pop the last destination airport from the sorted list (due to reverse sorting, popping the last element gives the smallest lexical element). Recursively call DFS on the popped destination airport.
6
Step 6: After visiting all reachable airports from the current airport, append the current airport to the itinerary list.
7
Step 7: Start the DFS from "JFK".
8
Step 8: Reverse the itinerary list to obtain the correct order, as the DFS adds airports in reverse order of traversal.
9
Step 9: Return the reversed itinerary.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(E)

💾

Space Complexity

O(E)

📝

Why?

The time complexity is dominated by the traversal of each ticket once. The space complexity is determined by the storage of the graph and the itinerary, both of which are proportional to the number of tickets.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Hierholzer's Algorithm

Hierholzer's algorithm is a more efficient approach specifically designed for finding Eulerian paths and circuits. It avoids recursion and uses a stack to keep track of the current path.

Time: O(E)Space: O(E)

Trade-offs: Hierholzer's algorithm is generally faster and more space-efficient than the DFS approach, especially for large graphs, as it avoids recursion overhead. However, the DFS approach with lexical sorting is easier to understand and implement for beginners.

✨

Key Insights

1Insight 1: The problem can be modeled as finding an Eulerian path/circuit in a directed graph, where airports are nodes and tickets are edges.
2Insight 2: The lexical order constraint requires sorting the destination airports in reverse lexicographical order before traversing the graph using Depth-First Search (DFS). This ensures the algorithm explores the smallest lexical order paths first.
3Insight 3: Using a data structure that allows efficient removal of edges (tickets) is crucial for performance. In Python, using `pop()` on a sorted list allows us to remove destinations in the desired order.

📚

Key Terms Explained

For Students

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: Multiple possible itineraries. The algorithm correctly handles this by sorting the destination airports in reverse lexicographical order, ensuring that the smallest lexical order path is explored first.
Edge case 2: Disconnected graphs (although the problem states a valid itinerary exists). The DFS algorithm ensures that all reachable nodes from 'JFK' are visited, and since a valid itinerary exists using ALL tickets, the disconnected nature is implicitly handled as part of a single Euler Path.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not sorting the destination airports in reverse lexicographical order. This will lead to incorrect itineraries that are not the smallest in lexical order.

✗Common mistake 2: Not reversing the itinerary at the end. The DFS algorithm constructs the itinerary in reverse order, so reversing it is crucial for obtaining the correct result.

✗Common mistake 3: Incorrectly handling the removal of edges. It's important to use a data structure that allows efficient removal of edges while maintaining the correct sorting order.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Route planning for delivery services or transportation networks. Finding the optimal route to visit all locations with minimal cost or distance, similar to finding an Eulerian path.

🏦Real-world scenario 2: Network routing in computer networks. Determining the path for data packets to traverse a network efficiently, visiting all nodes (routers) along the way.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 31, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

How do I represent a graph in code?

Use adjacency list (HashMap or array of lists) for sparse graphs - it's space-efficient O(V+E). Use adjacency matrix for dense graphs or when you need O(1) edge lookup. For weighted graphs, store (neighbor, weight) pairs in adjacency lists.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Reconstruct Itinerary"?

For this hard-level Depth-First Search problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether graph techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?