10 ms short Java Solution using DFS/topological sort, Beats 96 %. Well explained

  • 1
             * When you run random custom test cases in editor you will get to know that they require a topological sort to be done on the input.
             * For ex feeding [["JFK",NRT],["JFK",KUL]] returns ["JFK","NRT","KUL"] which seems wrong as per the explanation but since input is not a valid itinerary hence the result.
             * This problem needs a topological sort in short. Hence do a topological sort after storing nodes in a sorted order. 
             * Note :- 
             **Topological sort is used only for DAGs** hence we need to *remove the edges* once it is visited. Thats why the solution uses a priority queue which sorts the nodes as well as helps in removing it in an efficient way. 
            public List<String> findItinerary(String[][] tickets) {
                LinkedList<String> result = new LinkedList<>();
                HashMap<String,PriorityQueue<String>> graph = new HashMap<>();
                for(String[] edge : tickets){
                        graph.put(edge[0],new PriorityQueue<>());
                DFS("JFK",graph,result); // we need to do DFS/topological sort only from "JFK"
                return result;
            /*DFS doing topological sort*/
            private void DFS(String node,HashMap<String,PriorityQueue<String>> graph,LinkedList<String> result ){
                PriorityQueue<String> nodes = graph.get(node);
                while(nodes!= null && !nodes.isEmpty())
                result.addFirst(node); // this is the key, instead of reversing add to the head of linkelist.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.