Reconstruct Itinerary

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, priority_queue<string, vector<string>, greater<>>> g;
        for (auto& t : tickets) g[t[0]].push(t[1]);
        vector<string> route;
        function<void(const string&)> dfs = [&](const string& u) {
            auto& pq = g[u];
            while (!pq.empty()) {
                string v = pq.top(); pq.pop();
                dfs(v);
            }
            route.push_back(u);
        };
        dfs("JFK");
        reverse(route.begin(), route.end());
        return route;
    }
};

func findItinerary(tickets [][]string) []string {
    g := map[string][]string{}
    for _, t := range tickets {
        g[t[0]] = append(g[t[0]], t[1])
    }
    for k := range g {
        sort.Sort(sort.Reverse(sort.StringSlice(g[k])))
    }
    route := []string{}
    var dfs func(u string)
    dfs = func(u string) {
        for len(g[u]) > 0 {
            n := len(g[u])
            v := g[u][n-1]
            g[u] = g[u][:n-1]
            dfs(v)
        }
        route = append(route, u)
    }
    dfs("JFK")
    for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
        route[i], route[j] = route[j], route[i]
    }
    return route
}

import heapq
from collections import defaultdict
from typing import List

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        g: dict = defaultdict(list)
        for u, v in tickets:
            heapq.heappush(g[u], v)
        route: List[str] = []

        def dfs(u: str) -> None:
            while g[u]:
                v = heapq.heappop(g[u])
                dfs(v)
            route.append(u)

        dfs("JFK")
        route.reverse()
        return route

function findItinerary(tickets) {
    const g = new Map();
    for (const [u, v] of tickets) {
        if (!g.has(u)) g.set(u, []);
        g.get(u).push(v);
    }
    // Sort descending so we pop the smallest from the end in O(1).
    for (const arr of g.values()) arr.sort((a, b) => (a < b ? 1 : a > b ? -1 : 0));
    const route = [];
    const dfs = (u) => {
        const arr = g.get(u);
        while (arr && arr.length > 0) {
            const v = arr.pop();
            dfs(v);
        }
        route.push(u);
    };
    dfs("JFK");
    return route.reverse();
}

class Solution {
    private Map<String, PriorityQueue<String>> g;
    private List<String> route;

    public List<String> findItinerary(List<List<String>> tickets) {
        g = new HashMap<>();
        for (List<String> t : tickets) {
            g.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
        }
        route = new ArrayList<>();
        dfs("JFK");
        Collections.reverse(route);
        return route;
    }

    private void dfs(String u) {
        PriorityQueue<String> pq = g.get(u);
        while (pq != null && !pq.isEmpty()) {
            String v = pq.poll();
            dfs(v);
        }
        route.add(u);
    }
}

function findItinerary(tickets: string[][]): string[] {
    const g = new Map<string, string[]>();
    for (const [u, v] of tickets) {
        if (!g.has(u)) g.set(u, []);
        (g.get(u) as string[]).push(v);
    }
    // Sort descending so we pop the smallest from the end in O(1).
    for (const arr of g.values()) arr.sort((a, b) => (a < b ? 1 : a > b ? -1 : 0));
    const route: string[] = [];
    const dfs = (u: string): void => {
        const arr = g.get(u);
        while (arr && arr.length > 0) {
            const v = arr.pop() as string;
            dfs(v);
        }
        route.push(u);
    };
    dfs("JFK");
    return route.reverse();
}