Get Flight Itinerary

TIP102 Unit 10 Session 2 (Click for link to problem statements)

TIP103 Unit 5 Session 2 (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 25-35 mins
🛠️ Topics: Graph Traversal, DFS, Backtracking

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Q: What does the adjacency dictionary flights represent?
- A: Each key in flights is an airport, and the value is a list of airports that can be reached via direct flights from that key.
Q: Can there be multiple valid paths from source to destination?
- A: Yes, and the problem allows any valid path to be returned.
Q: What should be returned if no path is found?
- A: The function should return None if no valid path exists from source to destination.

HAPPY CASE
Input: 
flights = {
    'LAX': ['SFO'],
    'SFO': ['LAX', 'ORD', 'ERW'],
    'ERW': ['SFO', 'ORD'],
    'ORD': ['ERW', 'SFO', 'MIA'],
    'MIA': ['ORD']
}
source = 'LAX'
dest = 'MIA'

Output:
['LAX', 'SFO', 'ORD', 'MIA']
Explanation: The path LAX -> SFO -> ORD -> MIA is valid, though LAX -> SFO -> ERW -> ORD -> MIA is also valid.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Flight Itinerary problems, we want to consider the following approaches:

Depth First Search (DFS) with backtracking: This is ideal for exploring all possible paths from source to destination. DFS allows us to explore each path and backtrack if we reach a dead end.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all possible paths from the source airport to the destination. At each step, recursively attempt to extend the current path by exploring neighboring airports. If a valid path is found, return it. If no valid path is found, backtrack to explore alternative routes.

1) Define a recursive DFS function that takes the current airport and the current path as parameters.
2) If the current airport is the `destination`, return the current path.
3) If the current airport has no outgoing flights, return None.
4) For each neighboring airport, recursively attempt to extend the current path by visiting the neighbor.
   a) If a valid path is found, return it.
   b) If no valid path is found, backtrack and explore other neighbors.
     *** But be sure to create a visited check to avoid infinite loops! ***
5) Start DFS from the `source` airport.

⚠️ Common Mistakes

Assuming every airport appears as a key in flights — indexing flights[current] directly raises a KeyError when a dead-end airport is missing from the dictionary. Using flights.get(current, []) returns an empty list instead; note it is the visited set, not this guard, that prevents infinite loops on cyclic routes.
Forgetting to backtrack after exploring an invalid path, which can lead to incorrect results.

4: I-mplement

Implement the code to solve the algorithm.

def get_itinerary(flights, source, dest):
    visited = set()  # prevents cycling (e.g., LAX <-> SFO)

    def dfs(current, path):
        if current == dest:
            return path
        if current in visited:
            return None

        visited.add(current)
        for neighbor in flights.get(current, []):
            res = dfs(neighbor, path + [neighbor])
            if res:
                return res
        return None

    # Start DFS from the source
    return dfs(source, [source])

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

Input:

flights = {
    'LAX': ['SFO'],
    'SFO': ['LAX', 'ORD', 'ERW'],
    'ERW': ['SFO', 'ORD'],
    'ORD': ['ERW', 'SFO', 'MIA'],
    'MIA': ['ORD']
}

print(get_itinerary(flights, 'LAX', 'MIA'))  # Expected output: ['LAX', 'SFO', 'ORD', 'MIA']

Output:

['LAX', 'SFO', 'ORD', 'MIA']

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity: O(V + V * E) in the worst case, where V is the number of airports (vertices) and E is the number of flights (edges). The visited set ensures each airport is expanded at most once and each flight is tried at most once, but every recursive call builds a new list with path + [neighbor], an O(V) copy in the worst case, so the copies dominate the traversal itself.
Space Complexity: O(V^2) in the worst case: the recursion stack can be O(V) deep and each frame holds its own copy of the path, which can grow to V airports. Appending to and popping from a single shared path list instead would bring this down to O(V) and make the traversal O(V + E) time.