Reconstruct Itinerary

Hard

Netflix

5 views

Topics:

Graphs

You are given a list of airline tickets where tickets[i] = [fromi, toi] 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"]

Could you provide an algorithm to solve this problem efficiently? Consider edge cases and the time/space complexity of your solution.

Reconstruct Itinerary

Hard

Netflix

5 views

Topics:

Graphs

You are given a list of airline tickets where tickets[i] = [fromi, toi] 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"]

Could you provide an algorithm to solve this problem efficiently? Consider edge cases and the time/space complexity of your solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is it guaranteed that a valid itinerary exists given the input tickets?
If there are multiple valid itineraries, and some itineraries have the same smallest lexical order as a single string, which one should I return (e.g., the first one found, or is this impossible)?
What is the maximum number of tickets I can expect in the input? Should I be concerned about stack overflow for very deep itineraries?
Can the departure and arrival airports in the tickets list be any arbitrary string, or are there specific constraints on the characters or length of the airport codes?
If there are multiple tickets from the same departure airport, will the arrival airports for those tickets always be distinct?

Brute Force Solution

Approach

The brute force approach for reconstructing an itinerary involves trying every single possible route we could take between airports. We start at the beginning and exhaustively explore each path until we find one that visits all the required airports in the correct order based on the specified rules.

Here's how the algorithm would work step-by-step:

Start at the departure airport which is 'JFK'.
Look at all the possible flights leaving from 'JFK'.
Pick one of these flights and add it to your current itinerary.
Now, look at all the flights leaving from the destination airport of the flight you just added.
Pick one of these new flights and add it to your itinerary.
Keep doing this, adding flights to your itinerary one at a time.
If you reach a point where you have no more flights to take from your current airport, but you haven't used all the tickets, go back and try a different flight you skipped over earlier. Think of it like retracing your steps.
Once you've used all the tickets, check if your itinerary is valid, meaning it includes all the flights in the correct order based on alphabetical order when there are choices.
If the itinerary is valid, save it.
If you have multiple valid itineraries, compare them and pick the one that comes first alphabetically.
Keep trying all possible combinations of flights until you have explored every single option. You are guaranteed to find at least one valid itinerary because the prompt defines that there's always at least one solution.
Finally, return the itinerary that is earliest in alphabetical order from all the valid itineraries you've found.

Code Implementation

def reconstruct_itinerary_brute_force(tickets):
    all_itineraries = []
    number_of_tickets = len(tickets)

    def find_itineraries(current_airport, current_itinerary, used_tickets):
        # If all tickets have been used, check the validity and save
        if len(used_tickets) == number_of_tickets:
            all_itineraries.append(current_itinerary[:])
            return

        for index, ticket in enumerate(tickets):
            departure_airport, destination_airport = ticket

            if departure_airport == current_airport and index not in used_tickets:
                # Choose this flight and explore from the destination

                current_itinerary.append(destination_airport)
                used_tickets.add(index)

                find_itineraries(destination_airport, current_itinerary, used_tickets)

                # Backtrack: remove the flight to try other options
                current_itinerary.pop()
                used_tickets.remove(index)

    # Start from 'JFK' and explore all paths
    find_itineraries('JFK', ['JFK'], set())

    if not all_itineraries:
        return ['JFK']

    # Find the lexicographically smallest itinerary
    smallest_itinerary = sorted(all_itineraries)[0]

    return smallest_itinerary

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach explores all possible permutations of the given flight tickets. In the worst case, we might need to try every possible ordering of the tickets to find the correct itinerary. Since there are n tickets, there can be n! (n factorial) possible itineraries. Therefore, the time complexity is directly proportional to the number of possible permutations, resulting in O(n!).

Space Complexity

O(N) – The brute force approach described utilizes a temporary itinerary list to store the current path being explored, which could potentially contain all N tickets in the worst case. Additionally, the recursive calls made during backtracking could create a call stack with a maximum depth proportional to the number of tickets, N. Therefore, the auxiliary space used scales linearly with the number of tickets N, resulting in a space complexity of O(N).

Optimal Solution

Approach

To reconstruct the itinerary, we'll use a special way to explore the connections between the cities. Instead of guessing and checking, we will cleverly trace a path by always picking the next city in alphabetical order, ensuring we visit all cities.

Here's how the algorithm would work step-by-step:

Begin at the starting airport, which is always 'JFK'.
From your current location, find all possible destinations that you can fly to.
Among those choices, always select the airport that comes first alphabetically. This helps us get to the correct order without having to check many different options.
Once you choose the next airport, 'fly' there and remove that flight from your list of available flights.
Repeat the process: find the next set of possible airports, choose the one that comes first alphabetically, 'fly' there, and remove that flight.
Keep doing this until you run out of flights from a particular airport. When that happens, temporarily set aside the airport you are at.
Continue backtracking and making choices until all the flights are used up.
After you have used up all the flights, reverse the order in which you set aside airports to get the complete itinerary.
The itinerary will start with JFK and guide you through all the airports in the correct order.

Code Implementation

from collections import defaultdict

def reconstruct_itinerary(flights):
    flight_map = defaultdict(list)
    for start, end in flights:
        flight_map[start].append(end)

    for start in flight_map:
        flight_map[start].sort()

    itinerary = []

    def depth_first_search(airport):
        # While possible, keep visiting the next airport
        while flight_map[airport]:
            next_airport = flight_map[airport].pop(0)
            depth_first_search(next_airport)
        # Append to the beginning for correct order.
        itinerary.insert(0, airport)

    # Start at JFK as per instructions
    depth_first_search("JFK")

    return itinerary

Big(O) Analysis

Time Complexity

O(E log E) – The algorithm's runtime is primarily determined by the sorting of destinations from each airport and the removal of flight tickets. We can use a data structure such as a priority queue (implemented using a min-heap or similar) to store the destinations of each airport, which provides destinations in lexicographical order. For each of the V vertices (airports), we may iterate through all outgoing edges (flights). Sorting (implicitly via priority queue) the edges for each vertex takes O(E log E) time in the worst case, as each edge (flight) is inserted and extracted from the priority queue at most once. The backtracking process itself doesn't significantly impact the overall complexity, making O(E log E) the dominating factor.

Space Complexity

O(N) – The algorithm uses a data structure (implicitly a hash map or similar) to store the flights from each airport, where N is the number of flights. The recursion stack's maximum depth can also reach N in the worst-case scenario where the itinerary is a long chain, and we need to temporarily set aside the airports until we have used up all the flights. The itinerary itself, which stores the reconstructed path, grows proportionally to N. Thus, the dominant factor is the storage of flight data and the potentially deep recursion stack, leading to O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input tickets array	Return an empty list if the tickets array is empty, as there's no itinerary to construct.
Tickets array with a single ticket ["JFK", "XXX"]	The correct itinerary is ["JFK", "XXX"], which the algorithm should directly derive.
No valid itinerary exists (disconnected graph)	The algorithm must be able to detect a situation where it gets stuck and cannot reach all destinations, returning an empty list or indicating an error.
Multiple valid itineraries exist	The algorithm must ensure that among multiple valid itineraries, the lexicographically smallest one is returned by using a priority queue for airport selections.
Tickets forming a cycle, making a complete tour impossible	The algorithm, employing a depth-first search, must eventually exhaust all valid paths before concluding that no complete itinerary is possible or employ post-order traversal.
Input tickets contain the same departure and arrival (["AAA", "AAA"])	The algorithm should handle this case correctly, considering it as a valid hop in the itinerary.
Large input dataset causing stack overflow with recursion	The algorithm should consider iterative methods to avoid stack overflow exceptions and instead use a map to keep track of visited nodes and their next neighbors.
All tickets start from JFK, and they lead to the same destination.	The algorithm should correctly handle duplicate tickets, which affect visit count and lexicographical order if priority queue is used for neighbors.