#91 · Advanced Graphs

Reconstruct Itinerary

Given airline tickets as [from, to] pairs, reconstruct the itinerary that starts at "JFK" and uses every ticket exactly once. If several valid itineraries exist, return the one with the smallest lexical order.

HardLeetCode

Current
On path / queued
Done
Cycle / blocked

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Directed multigraph (adjacency lists)

Airports are nodes, tickets are directed edges, and the same ticket can appear more than once. Using every ticket exactly once means walking an Eulerian path from JFK. Sorting each airport's destination list gives the lexical order.

Memory layout

A hash map from airport to a list of destinations, E entries in total.

Operation	Cost
build + sort	O(E log E)

Stack (Hierholzer's algorithm)

Follow unused tickets greedily, always taking the smallest destination, until you get stuck. A stuck airport must be the end of the path, so it is written out and the walk resumes from the previous airport. Writing airports in post-order and reversing gives the Eulerian path.

Memory layout

An explicit stack of airports plus the output route, both at most E + 1 long.

Operation	Cost
each ticket flown once	O(E)

Why it fits

"Use every edge exactly once" is the definition of an Eulerian path, which Hierholzer's algorithm finds in linear time, without searching over orderings.
The greedy order (smallest destination first) can walk into a dead end, but post-order output places the dead end at the end of the route, so no backtracking is needed.
Popping from a descending-sorted list gives the smallest destination in O(1) and removes the ticket in the same step.

Why alternatives degrade

Greedy walk without post-order:: Taking the smallest destination can strand unused tickets behind a dead end (JFK → ABQ here).
Visited set of airports:: Airports are visited many times; it is the tickets that are used once.
Trying all permutations of tickets:: E! orders; backtracking prunes some, but can still be exponential.

Four approaches, from naive to production

1 · beginner

Backtracking over a sorted ticket list

time O(E!) worst casespace O(E)

Sort the tickets. From the current airport try each unused ticket in order, recurse, and undo the choice if the path cannot use all tickets.

vector<string> findItinerary(vector<vector<string>>& tickets) {
    vector<vector<string>> sorted(tickets);
    sort(sorted.begin(), sorted.end());
    vector<bool> used(sorted.size(), false);
    vector<string> path{"JFK"};
    function<bool()> dfs = [&]() -> bool {
        if (path.size() == sorted.size() + 1) return true;
        string from = path.back();
        for (size_t i = 0; i < sorted.size(); i++) {
            if (used[i] || sorted[i][0] != from) continue;
            used[i] = true;
            path.push_back(sorted[i][1]);
            if (dfs()) return true;
            path.pop_back();
            used[i] = false;
        }
        return false;
    };
    dfs();
    return path;
}

public List<String> findItinerary(List<List<String>> tickets) {
    List<List<String>> sorted = new ArrayList<>(tickets);
    sorted.sort((a, b) -> a.get(0).equals(b.get(0)) ? a.get(1).compareTo(b.get(1)) : a.get(0).compareTo(b.get(0)));
    boolean[] used = new boolean[sorted.size()];
    List<String> path = new ArrayList<>(); path.add("JFK");
    dfs(sorted, used, path);
    return path;
}
private boolean dfs(List<List<String>> sorted, boolean[] used, List<String> path) {
    if (path.size() == sorted.size() + 1) return true;
    String from = path.get(path.size() - 1);
    for (int i = 0; i < sorted.size(); i++) {
        if (used[i] || !sorted.get(i).get(0).equals(from)) continue;
        used[i] = true;
        path.add(sorted.get(i).get(1));
        if (dfs(sorted, used, path)) return true;
        path.remove(path.size() - 1);
        used[i] = false;
    }
    return false;
}

def find_itinerary(tickets):
    sorted_t = sorted(tickets)
    used = [False] * len(sorted_t)
    path = ['JFK']
    def dfs():
        if len(path) == len(sorted_t) + 1: return True
        frm = path[-1]
        for i in range(len(sorted_t)):
            if used[i] or sorted_t[i][0] != frm: continue
            used[i] = True
            path.append(sorted_t[i][1])
            if dfs(): return True
            path.pop()
            used[i] = False
        return False
    dfs()
    return path

function findItinerary(tickets: string[][]): string[] {
  const sorted = [...tickets].sort((a, b) => (a[0] === b[0] ? (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0) : a[0] < b[0] ? -1 : 1));
  const used = new Array<boolean>(sorted.length).fill(false);
  const path: string[] = ['JFK'];
  const dfs = (): boolean => {
    if (path.length === sorted.length + 1) return true;
    const from = path[path.length - 1];
    for (let i = 0; i < sorted.length; i++) {
      if (used[i] || sorted[i][0] !== from) continue;
      used[i] = true;
      path.push(sorted[i][1]);
      if (dfs()) return true;
      path.pop();
      used[i] = false;
    }
    return false;
  };
  dfs();
  return path;
}

Flaws & bottlenecks

Scans the whole ticket list at every step to find tickets from the current airport.
Exponential when there are many dead ends.
Needs an extra used[] array.

Interviewer cross-questions

Why does sorting give the lexically smallest itinerary?

Say: The first complete path found while trying destinations in ascending order is the smallest, because each choice is the smallest that still works.

When does backtracking trigger?

Say: When the path reaches an airport with no unused outgoing ticket before all tickets are used: a dead end that is not the final airport.

How do you avoid scanning all tickets?

Say: Group them by origin in a map of sorted lists.

2 · intermediate

Backtracking with sorted adjacency lists

time O(E!) worst casespace O(E)

Build graph[from] = sorted destinations. Take a destination out of the list, recurse, and put it back at the same index on failure.

vector<string> findItinerary(vector<vector<string>>& tickets) {
    unordered_map<string, vector<string>> graph;
    for (auto& t : tickets) {
        graph[t[0]].push_back(t[1]);
    }
    for (auto& [airport, list] : graph) sort(list.begin(), list.end());
    int total = tickets.size();
    vector<string> path{"JFK"};
    function<bool(const string&)> dfs = [&](const string& from) -> bool {
        if ((int)path.size() == total + 1) return true;
        vector<string>& list = graph[from];
        for (size_t i = 0; i < list.size(); i++) {
            string to = list[i]; list.erase(list.begin() + i);
            path.push_back(to);
            if (dfs(to)) return true;
            path.pop_back();
            list.insert(list.begin() + i, to);
        }
        return false;
    };
    dfs("JFK");
    return path;
}

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
    }
    for (List<String> list : graph.values()) Collections.sort(list);
    int total = tickets.size();
    List<String> path = new ArrayList<>(); path.add("JFK");
    dfs("JFK", graph, path, total);
    return path;
}
private boolean dfs(String from, Map<String, List<String>> graph, List<String> path, int total) {
    if (path.size() == total + 1) return true;
    List<String> list = graph.getOrDefault(from, new ArrayList<>());
    for (int i = 0; i < list.size(); i++) {
        String to = list.remove(i);
        path.add(to);
        if (dfs(to, graph, path, total)) return true;
        path.remove(path.size() - 1);
        list.add(i, to);
    }
    return false;
}

def find_itinerary(tickets):
    graph = defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    for lst in graph.values(): lst.sort()
    total = len(tickets)
    path = ['JFK']
    def dfs(frm):
        if len(path) == total + 1: return True
        lst = graph.get(frm, [])
        for i in range(len(lst)):
            to = lst.pop(i)
            path.append(to)
            if dfs(to): return True
            path.pop()
            lst.insert(i, to)
        return False
    dfs('JFK')
    return path

function findItinerary(tickets: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from)!.push(to);
  }
  for (const list of graph.values()) list.sort();
  const total = tickets.length;
  const path: string[] = ['JFK'];
  const dfs = (from: string): boolean => {
    if (path.length === total + 1) return true;
    const list = graph.get(from) ?? [];
    for (let i = 0; i < list.length; i++) {
      const to = list.splice(i, 1)[0];
      path.push(to);
      if (dfs(to)) return true;
      path.pop();
      list.splice(i, 0, to);
    }
    return false;
  };
  dfs('JFK');
  return path;
}

Flaws & bottlenecks

Array splice makes removal and reinsertion O(degree).
Still exponential on adversarial inputs.
Recursion depth equals the number of tickets.

Interviewer cross-questions

Why reinsert the ticket at the same index?

Say: To keep the list sorted so later attempts still try destinations in lexical order.

Is the first found itinerary the smallest?

Say: Yes, because destinations are tried in ascending order and the search is depth-first.

Can you avoid backtracking entirely?

Say: Yes: Hierholzer's algorithm uses post-order output so a dead end is simply written last.

3 · advanced

Hierholzer's algorithm (recursive)

time O(E log E)space O(E)

Sort each destination list descending. visit(airport) keeps flying the smallest unused ticket (list.pop()) recursively, and appends the airport to the route only when it has no tickets left. Reverse the route at the end.

vector<string> findItinerary(vector<vector<string>>& tickets) {
    unordered_map<string, vector<string>> graph;
    for (auto& t : tickets) {
        graph[t[0]].push_back(t[1]);
    }
    for (auto& [airport, list] : graph) sort(list.rbegin(), list.rend());
    vector<string> route;
    function<void(const string&)> visit = [&](const string& airport) {
        vector<string>& list = graph[airport];
        while (!list.empty()) { string to = list.back(); list.pop_back(); visit(to); }
        route.push_back(airport);
    };
    visit("JFK");
    reverse(route.begin(), route.end());
    return route;
}

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
    }
    for (List<String> list : graph.values()) list.sort(Collections.reverseOrder());
    LinkedList<String> route = new LinkedList<>();
    visit("JFK", graph, route);
    return route;
}
private void visit(String airport, Map<String, List<String>> graph, LinkedList<String> route) {
    List<String> list = graph.get(airport);
    while (list != null && !list.isEmpty()) visit(list.remove(list.size() - 1), graph, route);
    route.addFirst(airport);
}

def find_itinerary(tickets):
    graph = defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    for lst in graph.values(): lst.sort(reverse=True)
    route = []
    def visit(airport):
        lst = graph.get(airport)
        while lst: visit(lst.pop())
        route.append(airport)
    visit('JFK')
    return route[::-1]

function findItinerary(tickets: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from)!.push(to);
  }
  for (const list of graph.values()) list.sort().reverse();
  const route: string[] = [];
  const visit = (airport: string): void => {
    const list = graph.get(airport);
    while (list && list.length > 0) visit(list.pop()!);
    route.push(airport);
  };
  visit('JFK');
  return route.reverse();
}

Flaws & bottlenecks

Recursion depth can reach E (a long chain of tickets), which may overflow the stack.
The post-order trick is not intuitive.
Assumes a valid Eulerian path starting at JFK exists.

Interviewer cross-questions

Why is the route reversed?

Say: Airports are appended when they finish (post-order), so the path comes out last-to-first.

Why is the dead end placed correctly?

Say: A dead end can only be the final airport of the Eulerian path; it finishes first, so after reversing it is last.

What is the complexity?

Say: Sorting is O(E log E); every ticket is popped exactly once so the walk is O(E).

4 · expert

Iterative Hierholzer with validation

time O(E log E)space O(E)

Same algorithm with an explicit stack: peek the top, push the smallest unused destination if there is one, otherwise pop it to the route. Return the reversed route only if it contains tickets + 1 airports.

vector<string> findItinerary(vector<vector<string>>& tickets) {
    unordered_map<string, vector<string>> graph;
    for (auto& t : tickets) {
        graph[t[0]].push_back(t[1]);
    }
    for (auto& [airport, list] : graph) sort(list.rbegin(), list.rend());
    vector<string> stack{"JFK"};
    vector<string> route;
    while (!stack.empty()) {
        auto it = graph.find(stack.back());
        if (it != graph.end() && !it->second.empty()) {
            stack.push_back(it->second.back()); it->second.pop_back();
        } else {
            route.push_back(stack.back()); stack.pop_back();
        }
    }
    if (route.size() != tickets.size() + 1) return {};
    reverse(route.begin(), route.end());
    return route;
}

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
    }
    for (List<String> list : graph.values()) list.sort(Collections.reverseOrder());
    Deque<String> stack = new ArrayDeque<>(); stack.push("JFK");
    LinkedList<String> route = new LinkedList<>();
    while (!stack.isEmpty()) {
        List<String> list = graph.get(stack.peek());
        if (list != null && !list.isEmpty()) stack.push(list.remove(list.size() - 1));
        else route.addFirst(stack.pop());
    }
    return route.size() == tickets.size() + 1 ? route : new ArrayList<>();
}

def find_itinerary(tickets):
    graph = defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    for lst in graph.values(): lst.sort(reverse=True)
    stack = ['JFK']
    route = []
    while stack:
        lst = graph.get(stack[-1])
        if lst: stack.append(lst.pop())
        else: route.append(stack.pop())
    return route[::-1] if len(route) == len(tickets) + 1 else []

function findItinerary(tickets: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    const list = graph.get(from);
    if (list) list.push(to); else graph.set(from, [to]);
  }
  for (const list of graph.values()) list.sort().reverse();
  const stack: string[] = ['JFK'];
  const route: string[] = [];
  while (stack.length > 0) {
    const list = graph.get(stack[stack.length - 1]);
    if (list && list.length > 0) stack.push(list.pop()!);
    else route.push(stack.pop()!);
  }
  return route.length === tickets.length + 1 ? route.reverse() : [];
}

Flaws & bottlenecks

Still needs the O(E log E) sort for lexical order (a heap per airport has the same cost).
Input is assumed to start at JFK; a different start needs a parameter.
The length check detects only unusable ticket sets, not every invalid input.

Interviewer cross-questions

Why add the length check?

Say: If the tickets do not form a path from JFK that uses all of them, the route is shorter than tickets + 1; returning an empty list avoids an incorrect itinerary.

Why use an explicit stack?

Say: Itineraries can be 300 or more tickets long; an explicit stack removes any dependence on the recursion limit.

What are the edge cases?

Say: Duplicate tickets (keep both), a single ticket, self-loops (JFK → JFK), and airports that only appear as destinations.

Synchronized code walkthrough

Showing: Backtracking over a sorted ticket list — shares the player above; click any step to jump.

vector<string> findItinerary(vector<vector<string>>& tickets) {
    vector<vector<string>> sorted(tickets);
    sort(sorted.begin(), sorted.end());
    vector<bool> used(sorted.size(), false);
    vector<string> path{"JFK"};
    function<bool()> dfs = [&]() -> bool {
        if (path.size() == sorted.size() + 1) return true;
        string from = path.back();
        for (size_t i = 0; i < sorted.size(); i++) {
            if (used[i] || sorted[i][0] != from) continue;
            used[i] = true;
            path.push_back(sorted[i][1]);
            if (dfs()) return true;
            path.pop_back();
            used[i] = false;
        }
        return false;
    };
    dfs();
    return path;
}

public List<String> findItinerary(List<List<String>> tickets) {
    List<List<String>> sorted = new ArrayList<>(tickets);
    sorted.sort((a, b) -> a.get(0).equals(b.get(0)) ? a.get(1).compareTo(b.get(1)) : a.get(0).compareTo(b.get(0)));
    boolean[] used = new boolean[sorted.size()];
    List<String> path = new ArrayList<>(); path.add("JFK");
    dfs(sorted, used, path);
    return path;
}
private boolean dfs(List<List<String>> sorted, boolean[] used, List<String> path) {
    if (path.size() == sorted.size() + 1) return true;
    String from = path.get(path.size() - 1);
    for (int i = 0; i < sorted.size(); i++) {
        if (used[i] || !sorted.get(i).get(0).equals(from)) continue;
        used[i] = true;
        path.add(sorted.get(i).get(1));
        if (dfs(sorted, used, path)) return true;
        path.remove(path.size() - 1);
        used[i] = false;
    }
    return false;
}

def find_itinerary(tickets):
    sorted_t = sorted(tickets)
    used = [False] * len(sorted_t)
    path = ['JFK']
    def dfs():
        if len(path) == len(sorted_t) + 1: return True
        frm = path[-1]
        for i in range(len(sorted_t)):
            if used[i] or sorted_t[i][0] != frm: continue
            used[i] = True
            path.append(sorted_t[i][1])
            if dfs(): return True
            path.pop()
            used[i] = False
        return False
    dfs()
    return path

function findItinerary(tickets: string[][]): string[] {
  const sorted = [...tickets].sort((a, b) => (a[0] === b[0] ? (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0) : a[0] < b[0] ? -1 : 1));
  const used = new Array<boolean>(sorted.length).fill(false);
  const path: string[] = ['JFK'];
  const dfs = (): boolean => {
    if (path.length === sorted.length + 1) return true;
    const from = path[path.length - 1];
    for (let i = 0; i < sorted.length; i++) {
      if (used[i] || sorted[i][0] !== from) continue;
      used[i] = true;
      path.push(sorted[i][1]);
      if (dfs()) return true;
      path.pop();
      used[i] = false;
    }
    return false;
  };
  dfs();
  return path;
}

vector<string> findItinerary(vector<vector<string>>& tickets) {
    unordered_map<string, vector<string>> graph;
    for (auto& t : tickets) {
        graph[t[0]].push_back(t[1]);
    }
    for (auto& [airport, list] : graph) sort(list.begin(), list.end());
    int total = tickets.size();
    vector<string> path{"JFK"};
    function<bool(const string&)> dfs = [&](const string& from) -> bool {
        if ((int)path.size() == total + 1) return true;
        vector<string>& list = graph[from];
        for (size_t i = 0; i < list.size(); i++) {
            string to = list[i]; list.erase(list.begin() + i);
            path.push_back(to);
            if (dfs(to)) return true;
            path.pop_back();
            list.insert(list.begin() + i, to);
        }
        return false;
    };
    dfs("JFK");
    return path;
}

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
    }
    for (List<String> list : graph.values()) Collections.sort(list);
    int total = tickets.size();
    List<String> path = new ArrayList<>(); path.add("JFK");
    dfs("JFK", graph, path, total);
    return path;
}
private boolean dfs(String from, Map<String, List<String>> graph, List<String> path, int total) {
    if (path.size() == total + 1) return true;
    List<String> list = graph.getOrDefault(from, new ArrayList<>());
    for (int i = 0; i < list.size(); i++) {
        String to = list.remove(i);
        path.add(to);
        if (dfs(to, graph, path, total)) return true;
        path.remove(path.size() - 1);
        list.add(i, to);
    }
    return false;
}

def find_itinerary(tickets):
    graph = defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    for lst in graph.values(): lst.sort()
    total = len(tickets)
    path = ['JFK']
    def dfs(frm):
        if len(path) == total + 1: return True
        lst = graph.get(frm, [])
        for i in range(len(lst)):
            to = lst.pop(i)
            path.append(to)
            if dfs(to): return True
            path.pop()
            lst.insert(i, to)
        return False
    dfs('JFK')
    return path

function findItinerary(tickets: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from)!.push(to);
  }
  for (const list of graph.values()) list.sort();
  const total = tickets.length;
  const path: string[] = ['JFK'];
  const dfs = (from: string): boolean => {
    if (path.length === total + 1) return true;
    const list = graph.get(from) ?? [];
    for (let i = 0; i < list.length; i++) {
      const to = list.splice(i, 1)[0];
      path.push(to);
      if (dfs(to)) return true;
      path.pop();
      list.splice(i, 0, to);
    }
    return false;
  };
  dfs('JFK');
  return path;
}

vector<string> findItinerary(vector<vector<string>>& tickets) {
    unordered_map<string, vector<string>> graph;
    for (auto& t : tickets) {
        graph[t[0]].push_back(t[1]);
    }
    for (auto& [airport, list] : graph) sort(list.rbegin(), list.rend());
    vector<string> route;
    function<void(const string&)> visit = [&](const string& airport) {
        vector<string>& list = graph[airport];
        while (!list.empty()) { string to = list.back(); list.pop_back(); visit(to); }
        route.push_back(airport);
    };
    visit("JFK");
    reverse(route.begin(), route.end());
    return route;
}

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
    }
    for (List<String> list : graph.values()) list.sort(Collections.reverseOrder());
    LinkedList<String> route = new LinkedList<>();
    visit("JFK", graph, route);
    return route;
}
private void visit(String airport, Map<String, List<String>> graph, LinkedList<String> route) {
    List<String> list = graph.get(airport);
    while (list != null && !list.isEmpty()) visit(list.remove(list.size() - 1), graph, route);
    route.addFirst(airport);
}

def find_itinerary(tickets):
    graph = defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    for lst in graph.values(): lst.sort(reverse=True)
    route = []
    def visit(airport):
        lst = graph.get(airport)
        while lst: visit(lst.pop())
        route.append(airport)
    visit('JFK')
    return route[::-1]

function findItinerary(tickets: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    if (!graph.has(from)) graph.set(from, []);
    graph.get(from)!.push(to);
  }
  for (const list of graph.values()) list.sort().reverse();
  const route: string[] = [];
  const visit = (airport: string): void => {
    const list = graph.get(airport);
    while (list && list.length > 0) visit(list.pop()!);
    route.push(airport);
  };
  visit('JFK');
  return route.reverse();
}

vector<string> findItinerary(vector<vector<string>>& tickets) {
    unordered_map<string, vector<string>> graph;
    for (auto& t : tickets) {
        graph[t[0]].push_back(t[1]);
    }
    for (auto& [airport, list] : graph) sort(list.rbegin(), list.rend());
    vector<string> stack{"JFK"};
    vector<string> route;
    while (!stack.empty()) {
        auto it = graph.find(stack.back());
        if (it != graph.end() && !it->second.empty()) {
            stack.push_back(it->second.back()); it->second.pop_back();
        } else {
            route.push_back(stack.back()); stack.pop_back();
        }
    }
    if (route.size() != tickets.size() + 1) return {};
    reverse(route.begin(), route.end());
    return route;
}

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
    }
    for (List<String> list : graph.values()) list.sort(Collections.reverseOrder());
    Deque<String> stack = new ArrayDeque<>(); stack.push("JFK");
    LinkedList<String> route = new LinkedList<>();
    while (!stack.isEmpty()) {
        List<String> list = graph.get(stack.peek());
        if (list != null && !list.isEmpty()) stack.push(list.remove(list.size() - 1));
        else route.addFirst(stack.pop());
    }
    return route.size() == tickets.size() + 1 ? route : new ArrayList<>();
}

def find_itinerary(tickets):
    graph = defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    for lst in graph.values(): lst.sort(reverse=True)
    stack = ['JFK']
    route = []
    while stack:
        lst = graph.get(stack[-1])
        if lst: stack.append(lst.pop())
        else: route.append(stack.pop())
    return route[::-1] if len(route) == len(tickets) + 1 else []

function findItinerary(tickets: string[][]): string[] {
  const graph = new Map<string, string[]>();
  for (const [from, to] of tickets) {
    const list = graph.get(from);
    if (list) list.push(to); else graph.set(from, [to]);
  }
  for (const list of graph.values()) list.sort().reverse();
  const stack: string[] = ['JFK'];
  const route: string[] = [];
  while (stack.length > 0) {
    const list = graph.get(stack[stack.length - 1]);
    if (list && list.length > 0) stack.push(list.pop()!);
    else route.push(stack.pop()!);
  }
  return route.length === tickets.length + 1 ? route.reverse() : [];
}