Reconstruct Itinerary

Problem: Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

• If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
• All airports are represented by three capital letters (IATA code).
• You may assume all tickets form at least one valid itinerary.
• One must use all the tickets once and only once.

Example:

Input: [["EZE","AXA"],["TIA","ANU"],["ANU","JFK"],["JFK","ANU"],["ANU","EZE"], ["TIA","ANU"],["AXA","TIA"],["TIA","JFK"],["ANU","TIA"],["JFK","TIA"]]
Output: ["JFK","ANU","EZE","AXA","TIA","ANU","JFK","TIA","ANU","TIA","JFK"]

Approach: Basically we can make a graph from the given tickets and apply the DFS. There are two problems which we need to consider here:

1. In source to destinations mapping, we need to keep destinations in sorted order.
2. There could be duplicate tickets here like in the above example you can see ["TIA", "ANU"] came 2 times so if you are going to use DS like C# SortedSet to store destinations in sorted order. Don't do it!

 

Implementation in C#:

        public static IList<string> FindItinerary(IList<IList<string>> tickets)

        {

            List<string> result = new List<string>();

            const string startStation = "JFK";

            if (tickets?.Count == 0)

            {

                return result;

            }

            Dictionary<string, List<string>> sourceDestinationsMap = new Dictionary<string, List<string>>();

            foreach(var ticket in tickets)

            {

                if (!sourceDestinationsMap.ContainsKey(ticket.First()))

                {

                    sourceDestinationsMap.Add(ticket.First(), new List<string>());

                }

                sourceDestinationsMap[ticket.First()].Add(ticket.Last());

            }

            foreach (string key in sourceDestinationsMap.Keys)

            {

                sourceDestinationsMap[key].Sort();

            }

            FindItineraryDFS(startStation, sourceDestinationsMap, result);

            result.Reverse();

            return result;

        }

        private static void FindItineraryDFS(string source, Dictionary<string, List<string>> sourceDestinationsMap, List<string> result)

        {

            while(sourceDestinationsMap.ContainsKey(source) && sourceDestinationsMap[source].Count > 0)

            {

                string destination = sourceDestinationsMap[source].First();

                sourceDestinationsMap[source].Remove(destination);

                

                FindItineraryDFS(destination, sourceDestinationsMap, result);

            }

            result.Add(source);

        }

Complexity: O(nlogn)