Algorithm Solution: Reconstruct Itinerary

gui commited 4 years ago

As part of my goals this year, I wished to practice a bit more on solving algorithm challenges. I'll share my solutions and aha moments first as a reference to myself, and last as a possible resource to help other people studying it either.

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. [...]

Complete problem description can be found here: https://leetcode.com/problems/reconstruct-itinerary/

Solution

from collections import defaultdict

STARTING_ORIGIN = "JFK"
ROUTES_INPUT = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

class Solution:
    def findItinerary(cls, tickets: list[list[str]]) -> list[str]:
        flights = defaultdict(list)
        
        for origin, to in sorted(tickets):
            flights[origin].append(to)            
            
        step_stack = []
        result_stack = []
        stop = STARTING_ORIGIN
        
        while stop:
            if flights[stop]:                
                step_stack.append(stop)            
                nextstop = flights[stop].pop(0)
                print(f"✅ {stop} has a next stop {nextstop} so worth getting into it!")
                stop = nextstop
            else:                
                result_stack.append(stop)
                stop = step_stack.pop() if step_stack else None
                print(f"❌ There's no way out from {result_stack[-1]} so I'm getting back to {stop}")                
                
        return result_stack[::-1]

Solution().findItinerary(ROUTES_INPUT)

Explanation

Setup

Some tricks that make this exercise easier:

Using defaultdict avoids me from checking whether the dict entry exists - so I can always append
Sorting the list with sorted makes me ensure I will visit (as a queue) the tickets in the lexical order as required by the problem

Algorithm

Cool, the data is set, so we can dive into the solution. I assign the first stop as JFK because that's the rule and I start considering every next step.

As long as my stop has a next one - so I get into it. Notice it doesn't mean I'm building my result.

Actually, I can only start building my result as soon as there's nowhere else to go because it means it's a dead end (or final stop).

Simulation

So considering the following input: [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]] that should give the result:

You may notice that KUL comes before NRT in lexical order, so we visit KUL first. As soon as we realize KUL there's no next stop we find out that KUL is our final stop!!

That's why the result is a stack, we're building it in a reverse way!

After finding the final stop, we use our step_stack to go back one stop and see where we can go from there - and the cycle keeps going.

Remember to always pop from our flights so we never visit the same place more than we can!