# Reconstruct Itinerary Solution Guide

### General overview of the solution
This is categorized as a “medium” level question on leetcode, but this a pretty challenging problem. Even after realizing it is a graph problem, coming up with the correct algorithm is challenging.

We first construct a directed graph where nodes are airports and edges are tickets. A key idea is that we know that airports with no outgoing edges will appear at the end of the itinerary because it signifies you’ve reached the final destination. For example, let’s assume that SFO has no outgoing edges and ATL is the only airport with a ticket to SFO. We therefore know that ATL appears second-to-last in the itinerary. Thus, it makes sense to build up the itinerary backwards.

To accomplish this, we traverse the graph with a DFS and maintain a stack of airports we are currently visiting. When we traverse an edge, we remove it from the graph (using up that particular ticket). Importantly, we only pop an airport off the stack and add it to the end of our itinerary when it has no more outgoing edges (i.e. all of the tickets leaving the airport have been used).

At the end, because we have been constructing this itinerary backwards, we need to reverse order the itinerary before returning it.

### Solution: Python

def find_itinerary(tickets):
    ticket_graph = defaultdict(list)
    sorted_tickets = sorted(tickets)
    for start, end in sorted_tickets:
        ticket_graph[start].append(end)
    route = []
    visit('JFK', ticket_graph, route)
    route.reverse()
    return route


def visit(airport, ticket_graph, route):
    while ticket_graph[airport]:
        next_city = ticket_graph[airport].pop(0)
        visit(next_city, ticket_graph, route)
    route.append(airport)

After looking at the solution, you should try and run through a few examples to see how the code works and why it works. Try drawing out an example graph and running the algorithm on it.


### Complexity Analysis
* Time complexity: O(n log n)
* Space complexity: O(n)

###### tags: `Week 5-Graphs`