Hierholzer

Use Hierholzer’s Algorithm because this is basically:
“Use every ticket exactly once and build valid path in lexical order.”

Approach: Hierholzer’s Algorithm (Eulerian Path)

Time: O(E log E) Space: O(E)

class Solution {
  /**
   * @param {string[][]} tickets
   * @return {string[]}
   */
  findItinerary(tickets) {
    const adj = new Map();
 
    // Sort reverse lexical so we can pop smallest destination later
    tickets.sort((a, b) => b[1].localeCompare(a[1]));
 
    for (const [src, dst] of tickets) {
      if (!adj.has(src)) adj.set(src, []);
      adj.get(src).push(dst);
    }
 
    const result = [];
 
    const dfs = (src) => {
      const neighbors = adj.get(src) || [];
 
      while (neighbors.length > 0) {
        const next = neighbors.pop(); // smallest lexical destination
        dfs(next);
      }
 
      result.push(src);
    };
 
    dfs("JFK");
 
    return result.reverse();
  }
}

Why this works

We keep going deeper while tickets are available.
When a city has no more outgoing flights, we add it to result.

This builds the path backwards, so finally we reverse it.

Complexity

Time: O(E log E)
Space: O(E)

E = number of tickets

Sorting takes O(E log E), DFS uses each ticket once.

Lexicographical Order Optimization

• We need the lexicographically smallest destination first.
• shift() is O(n) because all remaining elements must be re-indexed.
• Sort destinations in descending lexicographical order.
• Use pop() to retrieve the smallest destination in O(1) time.
• This avoids the extra cost of repeated shift() operations and keeps traversal efficient.

Example:

["SFO", "MUC", "ATL"] // descending
pop() => "ATL"        // smallest lexical destination
 

---

Why pop()?

• pop() removes the destination from the adjacency list.
• Once removed, that ticket can never be used again.
• This naturally satisfies the requirement that every ticket must be used exactly once.
• No separate visited set is needed because consuming the edge removes it from the graph.

Example:

adj["JFK"] = ["SFO", "ATL"];
 
adj["JFK"].pop(); // "ATL"
 
adj["JFK"] = ["SFO"]; // ATL ticket is gone forever

---

Usual DFS	Hierholzer’s DFS
Goal: Visit nodes	Goal: Use every edge exactly once
Tracks visited nodes	Tracks/consumes edges
Process node when first seen (preorder)	Process node after all edges are exhausted (postorder)
Node usually visited once	Node may be visited many times
Used for reachability, components, cycles, etc.	Used for Eulerian Path/Circuit problems
Usually keeps graph unchanged	Removes/consumes edges during traversal

Normal DFS

dfs(A)
  visit A
  dfs(B)
  dfs(C)

You add the node when you arrive.

---

Hierholzer DFS

dfs(A)
  while(edges exist)
     dfs(next)
 
  result.push(A)

You add the node when leaving, after all outgoing edges are used.

---

Example

Tickets:

JFK -> ATL
ATL -> SFO
SFO -> JFK

Normal DFS order:

JFK, ATL, SFO

Hierholzer builds:

JFK, SFO, ATL, JFK

(backwards)

Then reverse:

JFK, ATL, SFO, JFK

Final itinerary.

---

Interview One-Liner

Hierholzer's Algorithm is a modified DFS for finding an Eulerian Path/Circuit. Unlike normal DFS which marks nodes visited, it consumes edges and adds nodes to the answer during backtracking, producing the path in reverse order.