LeetCode 332 - Reconstruct Itinerary

import java.util.*;

/**
 * LeetCode 332 - Reconstruct Itinerary
 * 
 * Problem: Given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure
 * and arrival airports, reconstruct the itinerary in order. All tickets belong to a person who
 * departs from "JFK". If there are multiple valid itineraries, return the itinerary with the
 * smallest lexical order when read as a single string.
 * 
 * Approach: Hierholzer's Algorithm for Eulerian Path
 * 1. Build an adjacency list using PriorityQueue to maintain lexical ordering
 * 2. Perform DFS with backtracking to find the Eulerian path
 * 3. Reverse the result as we add airports in reverse order during DFS
 * 
 * Time Complexity: O(E * log E) where E is the number of tickets
 * Space Complexity: O(E) for the adjacency list and recursion stack
 */
class Solution {
    // Adjacency list to store the graph
    private Map<String, PriorityQueue<String>> flights;
    // List to store the final itinerary
    private List<String> itinerary;

    /**
     * Finds the itinerary starting from JFK visiting all airports.
     * 
     * @param tickets List of tickets where each ticket is [from, to]
     * @return List of airports in the order they should be visited
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        flights = new HashMap<>();
        itinerary = new LinkedList<>();

        // Build the graph using adjacency list
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            flights.putIfAbsent(from, new PriorityQueue<>());
            flights.get(from).offer(to);
        }

        // Start DFS from JFK
        dfs("JFK");

        // Reverse the itinerary as we added airports in reverse order
        Collections.reverse(itinerary);
        return itinerary;
    }

    /**
     * Performs DFS traversal to find Eulerian path.
     * Uses Hierholzer's algorithm to find the path visiting all edges exactly once.
     * 
     * @param airport Current airport in the DFS traversal
     */
    private void dfs(String airport) {
        // Get the queue of destinations from current airport
        PriorityQueue<String> destinations = flights.get(airport);

        // Continue visiting next airports until no more destinations
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll());
        }

        // Add current airport to itinerary (in reverse order)
        itinerary.add(airport);
    }
}

Test Case

import java.util.*;

public class ReconstructItineraryTest {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test Case 1: Simple path
        List<List<String>> tickets1 = Arrays.asList(
            Arrays.asList("JFK", "SFO"),
            Arrays.asList("SFO", "LAX")
        );
        System.out.println("Test Case 1 - Simple Path:");
        System.out.println("Input: " + tickets1);
        System.out.println("Output: " + solution.findItinerary(tickets1));
        // Expected: [JFK, SFO, LAX]

        // Test Case 2: Multiple possible paths, should return lexicographically smallest
        List<List<String>> tickets2 = Arrays.asList(
            Arrays.asList("JFK", "SFO"),
            Arrays.asList("JFK", "ATL"),
            Arrays.asList("SFO", "ATL"),
            Arrays.asList("ATL", "JFK"),
            Arrays.asList("ATL", "SFO")
        );
        System.out.println("\nTest Case 2 - Multiple Paths:");
        System.out.println("Input: " + tickets2);
        System.out.println("Output: " + solution.findItinerary(tickets2));
        // Expected: [JFK, ATL, JFK, SFO, ATL, SFO]

        // Test Case 3: Circular path
        List<List<String>> tickets3 = Arrays.asList(
            Arrays.asList("JFK", "KUL"),
            Arrays.asList("KUL", "JFK")
        );
        System.out.println("\nTest Case 3 - Circular Path:");
        System.out.println("Input: " + tickets3);
        System.out.println("Output: " + solution.findItinerary(tickets3));
        // Expected: [JFK, KUL, JFK]
    }
}