Problem statement

https://binarysearch.com/problems/Flight-Itinerary-Sequel/

Solution

Variation of Leetcode 0332. Reconstruct Itinerary, but here we also need to choose the starting city. If we have all degrees even, we choose the smallest city, if not, we have only one option.

Complexity

It is O(E log E) for time and O(E + n) for space.

Code

class Solution:
    def solve(self, tickets):
        def dfs(airport):
            while graph[airport]:
                candidate = graph[airport].pop()
                dfs(candidate)
            route.append(airport)
        
        route, cands = [], []
        graph = defaultdict(list)
        deg = Counter()
        for i, j in tickets:
            graph[i].append(j)
            deg[i] += 1
            deg[j] -= 1

        for key in graph: 
            graph[key] = sorted(graph[key], reverse=True)

        start = sorted(x for x in graph)[0]
        for x in deg:
            if deg[x] == 1:
                start = x
                break

        dfs(start)
        return route[::-1]