Posts Reconstruct Itinerary
Post
Cancel

Reconstruct Itinerary

Problem Description

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. 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”].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

leetcode

Solution

The idea to solve this problem is simple but the implementation is a bit tricky. Here, we have used DFS to check the path. It’s possible that the next node (destination) that we pick up will not lead to any solution, in which case, we need to backtrack and check the next destination.

A good test case:

[[“JFK”,”KUL”],[“JFK”,”NRT”],[“NRT”,”JFK”]]

The result for this test case will be:

[“JFK”,”NRT”,”JFK”,”KUL”]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution {
    
    public List<String> findItinerary(List<List<String>> tickets) {

        //Create an adjacency list using tickets
        //<String, List<String>> : <Source, Neighbours>
        Map<String, List<String>> g = new HashMap<>();

        for(int i=0; i<tickets.size(); i++){

            String source = tickets.get(i).get(0);
            String destination = tickets.get(i).get(1);

            if(g.get(source) == null){
                List<String> t = new ArrayList<>();
                t.add(destination);
                g.put(source, t);
            }else{
                g.get(source).add(destination);
            }

        }

        //We need to return the path which comes first in lexical order
        //So, sort the list of neighbours
        for(java.util.Map.Entry e: g.entrySet()){
            Collections.sort((List<String>)e.getValue());
        }

        //DFS with backtracking
        //The number of nodes in path must be number of tickets + 1
        //Number of tickets represent edges
        travel(g, new ArrayList<String>(Arrays.asList("JFK")), "JFK", tickets.size()+1);

        //Return the first path from all pathsPossible
        return pathsPossible.get(0);

    }

    List<List<String>> pathsPossible = new ArrayList<>();

    public List<String> travel(Map<String, List<String>> g, List<String> path, String source, int size){

        //We can remove this line to get a list of all possible paths
        //This leads to memory out of limit though
        //To handle that, we will just return when we've found our first path which is what we ultimately need to return
        if(pathsPossible.size() > 0) return path;

        //base consition
        //if all edges have been used
        if(path.size() == size){
            pathsPossible.add(new ArrayList<>(path));
            return path;
        }

        //get the neighbours of current source
        List<String> neighbours = g.get(source);

        //if there are no neighbours, return
        if(neighbours == null || neighbours.size() == 0) return path;

        //otherwise, try out each neighbour to see if that path is possible
        for(int i=0; i<neighbours.size(); i++){
            
            //store next node to visit
            String next = neighbours.get(i);
            
            //add it to the path
            path.add(next);

            //remove it from neighbours so that we don't use that edge (which represents ticket) again
            g.get(source).remove(next);

            //call DFS recursively using the this node
            travel(g, path, next, size);
            
            //backtrack
            //add the node back to it's sorted order
            g.get(source).add(i, next); 

            //remove the node from path and try other nodes
            path.remove(path.size()-1);

        }

        return path;

    }

}
This post is licensed under CC BY 4.0 by the author.