Reconstruct Itinerary

                                            
class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, multiset<string>> graph;
        vector<string> result;
        
        for (const auto& ticket : tickets) {
            graph[ticket[0]].insert(ticket[1]);
        }
        
        function<void(string)> dfs = [&](string src) {
            while (!graph[src].empty()) {
                string dest = *graph[src].begin();
                graph[src].erase(graph[src].begin());
                dfs(dest);
            }
            result.push_back(src);
        };
        
        dfs("JFK");
        
        reverse(result.begin(), result.end());
        
        return result;
    }
};

                                            
class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        List<String> result = new ArrayList<>();
        
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            graph.putIfAbsent(from, new PriorityQueue<>());
            graph.get(from).offer(to);
        }
        
        dfs("JFK", graph, result);
        
        return result;
    }
    
    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> result) {
        PriorityQueue<String> pq = graph.get(airport);
        
        while (pq != null && !pq.isEmpty()) {
            dfs(pq.poll(), graph, result);
        }
        
        result.add(0, airport);
    }
}

                                            
class Solution(object):
    def findItinerary(self, tickets):
        def dfs(curr):
            while graph[curr]:
                dfs(graph[curr].pop(0))
            result.append(curr)
        
        graph = collections.defaultdict(list)
        for ticket in sorted(tickets):
            graph[ticket[0]].append(ticket[1])
        
        result = []
        dfs("JFK")
        
        return result[::-1]

                                            
public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var graph = new Dictionary<string, List<string>>();
        var result = new List<string>();

        foreach (var ticket in tickets) {
            if (!graph.ContainsKey(ticket[0])) {
                graph[ticket[0]] = new List<string>();
            }
            graph[ticket[0]].Add(ticket[1]);
        }

        foreach (var pair in graph) {
            pair.Value.Sort();
        }

        Visit("JFK");

        result.Reverse();
        return result;

        void Visit(string airport) {
            while (graph.ContainsKey(airport) && graph[airport].Count > 0) {
                var dest = graph[airport][0];
                graph[airport].RemoveAt(0);
                Visit(dest);
            }
            result.Add(airport);
        }
    }
}

                                            
/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function(tickets) {
    let adjList = {};
    for (let ticket of tickets) {
        if (!adjList[ticket[0]]) {
            adjList[ticket[0]] = [];
        }
        adjList[ticket[0]].push(ticket[1]);
    }

    for (let list in adjList) {
        adjList[list].sort();
    }

    let result = [];

    const dfs = (node) => {
        let neighbors = adjList[node];
        while (neighbors && neighbors.length) {
            dfs(neighbors.shift());
        }
        result.unshift(node);
    };

    dfs('JFK');

    return result;
};

                                            
function findItinerary(tickets: string[][]): string[] {
    const graph: { [key: string]: string[] } = {};
    const result: string[] = [];

    tickets.forEach(([from, to]) => {
        if (graph[from]) {
            graph[from].push(to);
        } else {
            graph[from] = [to];
        }
    });

    Object.values(graph).forEach((connections) => connections.sort());

    const dfs = (node: string) => {
        while (graph[node] && graph[node].length > 0) {
            const next = graph[node].shift();
            dfs(next);
        }
        result.unshift(node);
    };

    dfs('JFK');

    return result;
};

                                            
class Solution {
    /**
     * @param String[][] $tickets
     * @return String[]
     */
    function findItinerary($tickets) {
        $graph = [];
        foreach ($tickets as $ticket) {
            $from = $ticket[0];
            $to = $ticket[1];
            if (!isset($graph[$from])) {
                $graph[$from] = [];
            }
            $graph[$from][] = $to;
        }
        
        foreach ($graph as $from => $to) {
            sort($graph[$from]);
        }
        
        $result = [];
        $this->dfs($graph, 'JFK', $result);
        
        return $result;
    }
    
    function dfs(&$graph, $from, &$result) {
        while (isset($graph[$from]) && count($graph[$from]) > 0) {
            $to = array_shift($graph[$from]);
            $this->dfs($graph, $to, $result);
        }
        array_unshift($result, $from);
    }
}

                                            
class Solution {
    fun findItinerary(tickets: List<List<String>>): List<String> {
        val graph = mutableMapOf<String, MutableList<String>>()
        val result = mutableListOf<String>()

        for (ticket in tickets) {
            val from = ticket[0]
            val to = ticket[1]
            if (!graph.containsKey(from)) {
                graph[from] = mutableListOf()
            }
            graph[from]!!.add(to)
        }

        for (key in graph.keys) {
            graph[key]!!.sort()
        }

        fun dfs(city: String) {
            while (graph.containsKey(city) && graph[city]!!.isNotEmpty()) {
                val nextCity = graph[city]!!.removeAt(0)
                dfs(nextCity)
            }
            result.add(0, city)
        }

        dfs("JFK")

        return result
    }
}

                                            
class Solution {
  List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = {};
    List<String> result = [];

    for (List<String> ticket in tickets) {
      graph.putIfAbsent(ticket[0], () => []).add(ticket[1]);
    }

    for (List<String> destinations in graph.values) {
      destinations.sort();
    }

    void dfs(String source) {
      while (graph.containsKey(source) && graph[source]!.isNotEmpty) {
        String destination = graph[source]!.removeAt(0);
        dfs(destination);
      }
      result.insert(0, source);
    }

    dfs('JFK');

    return result;
  }
}

                                            
func findItinerary(tickets [][]string) []string {
    graph := make(map[string][]string)
    result := []string{}
    
    for _, ticket := range tickets {
        graph[ticket[0]] = append(graph[ticket[0]], ticket[1])
    }
    
    for key := range graph {
        sort.Strings(graph[key])
    }
    
    var dfs func(string)
    dfs = func(origin string) {
        for {
            if destinations, ok := graph[origin]; !ok || len(destinations) == 0 {
                break
            }
            nextDest := graph[origin][0]
            graph[origin] = graph[origin][1:]
            dfs(nextDest)
        }
        result = append([]string{origin}, result...)
    }
    
    dfs("JFK")
    
    return result
}

                                            
# @param {String[][]} tickets
# @return {String[]}
def find_itinerary(tickets)
    graph = Hash.new { |h, k| h[k] = [] }
    tickets.each { |from, to| graph[from] << to }
    graph.values.each(&:sort!)
    
    result = []
    stack = ['JFK']
    
    while stack.any?
        if graph[stack.last].empty?
            result.unshift(stack.pop)
        else
            stack.push(graph[stack.last].shift)
        end
    end
    
    result
end

To solve this coding challenge, we need to reconstruct an itinerary from given airline tickets where the reconstruction must start from "JFK" and use all the given tickets exactly once. The desired itinerary should also be the lexicographically smallest one if multiple valid itineraries exist.

Explanation

The problem can be approached effectively by using a Depth-First Search (DFS) algorithm. The main idea is to form the itinerary by recursively exploring possible flights and backtracking to ensure all tickets are used exactly once. Here's a detailed breakdown of the steps involved:

Graph Representation :

We represent the flights in a graph where each node is an airport and each directed edge is a flight.

For each ticket, the departure airport is connected to the arrival airport.
We'll use a dictionary data structure to represent the graph, where each key is a departure airport, and the value is a list of arrival airports.

Sorting :

To guarantee that we get the itinerary in the lexicographically smallest order, we need to ensure that we always choose the smallest possible airport first when there are multiple options. This can be achieved by sorting the list of arrival airports for each departure airport.

Depth-First Search with Backtracking :

We start the DFS from "JFK".
Visit an airport, then recursively visit its neighbors (i.e., the airports it has flights to), removing the edge (or ticket) as we go. This mimics the use of the ticket.
Append the airport to the results list once all its neighbors have been visited.

Reversing the Result :

Since we are inserting airports in post-order traversal of the graph (i.e., after visiting all possible outgoing flights), the final result will be in reverse order. Hence, we need to reverse the result list at the end.

Here is the pseudocode that outlines this approach:

                                            
# Function to find the itinerary starting from JFK
function findItinerary(tickets):
# Create a graph as a dictionary where keys are departure airports
# and values are lists of arrival airports
graph = empty dictionary with lists as default values

# Populate the graph with sorted tickets to ensure lexicographical order
for each ticket in sorted(tickets):
add the arrival airport to the list of the departure airport in the graph

# Initialize an empty list to store the result itinerary
result = empty list

# Helper function to perform DFS
function dfs(current_airport):
while there are flights from current_airport in the graph:
# Choose the lexicographically smallest airport
next_airport = the first airport in the list of current_airport in the graph
# Recursively visit the next airport
dfs(next_airport)
# Once all flights from the current airport are processed, add it to the result
append current_airport to result

# Start the DFS from 'JFK'
dfs("JFK")

# Since the result list is built in reverse order, reverse it to get the correct itinerary
return reversed result

# Test the function with an example
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
print(findItinerary(tickets))  # Expected Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Detailed Steps in Pseudocode

Graph Initialization :

Create a dictionary
graph

with default list values.
Iterate through the sorted list of tickets and populate the
graph

.

                                            
graph = {}
for ticket in sorted(tickets):
departure, arrival = ticket
if departure not in graph:
graph[departure] = []
graph[departure].append(arrival)

Defining the DFS function :

Define a recursive function
dfs

that takes the current airport as an argument.
While the current airport has outgoing flights, choose the smallest next airport and recursively visit it.
Append the current airport to the result after visiting all its neighbors.

                                            
function dfs(current_airport):
while graph[current_airport]:
next_airport = graph[current_airport].pop(0)
dfs(next_airport)
result.append(current_airport)

Executing DFS from 'JFK' and reversing the result :

Initialize the result list and call
dfs

with the initial airport 'JFK'.
Reverse the result list to get the correct order of the itinerary.

                                            
result = []
dfs("JFK")
return result[::-1]

With these steps, the desired itinerary is constructed ensuring that we use all tickets exactly once and the itinerary is lexicographically smallest.