Find Itinerary from a given list of tickets
Last Updated :
03 Apr, 2024
Given a list of tickets, find itinerary in order using the given list.
Example:
Input:
"Chennai" -> "Banglore"
"Bombay" -> "Delhi"
"Goa" -> "Chennai"
"Delhi" -> "Goa"
Output:
Bombay->Delhi, Delhi->Goa, Goa->Chennai, Chennai->Banglore,
It may be assumed that the input list of tickets is not cyclic and there is one ticket from every city except the final destination.
One Solution is to build a graph and do Topological Sorting of the graph. The time complexity of this solution is O(n).
We can also use hashing to avoid building a graph. The idea is to first find the starting point. A starting point would never be on ‘to’ side of a ticket. Once we find the starting point, we can simply traverse the given map to print itinerary in order. The following are steps.
1) Create a HashMap of given pair of tickets. Let the created
HashMap be 'dataset'. Every entry of 'dataset' is of the form
"from->to" like "Chennai" -> "Banglore"
2) Find the starting point of itinerary.
a) Create a reverse HashMap. Let the reverse be 'reverseMap'
Entries of 'reverseMap' are of the form "to->form".
Following is 'reverseMap' for above example.
"Banglore"-> "Chennai"
"Delhi" -> "Bombay"
"Chennai" -> "Goa"
"Goa" -> "Delhi"
b) Traverse 'dataset'. For every key of dataset, check if it
is there in 'reverseMap'. If a key is not present, then we
found the starting point. In the above example, "Bombay" is
starting point.
3) Start from above found starting point and traverse the 'dataset'
to print itinerary.
All of the above steps require O(n) time so overall time complexity is O(n).
Below is Java implementation of above idea.
C++
#include <bits/stdc++.h>
using namespace std;
void printItinerary(map<string, string> dataSet)
{
map<string, string> reversemap;
map<string, string>::iterator it;
for (it = dataSet.begin(); it!=dataSet.end(); it++)
reversemap[it->second] = it->first;
string start;
for (it = dataSet.begin(); it!=dataSet.end(); it++)
{
if (reversemap.find(it->first) == reversemap.end())
{
start = it->first;
break;
}
}
if (start.empty())
{
cout << "Invalid Input" << endl;
return;
}
it = dataSet.find(start);
while (it != dataSet.end())
{
cout << it->first << "->" << it->second << endl;
it = dataSet.find(it->second);
}
}
int main()
{
map<string, string> dataSet;
dataSet["Chennai"] = "Banglore";
dataSet["Bombay"] = "Delhi";
dataSet["Goa"] = "Chennai";
dataSet["Delhi"] = "Goa";
printItinerary(dataSet);
return 0;
}
|
Java
import java.util.HashMap;
import java.util.Map;
public class printItinerary
{
public static void main(String[] args)
{
Map<String, String> dataSet = new HashMap<String, String>();
dataSet.put("Chennai", "Banglore");
dataSet.put("Bombay", "Delhi");
dataSet.put("Goa", "Chennai");
dataSet.put("Delhi", "Goa");
printResult(dataSet);
}
private static void printResult(Map<String, String> dataSet)
{
Map<String, String> reverseMap = new HashMap<String, String>();
for (Map.Entry<String,String> entry: dataSet.entrySet())
reverseMap.put(entry.getValue(), entry.getKey());
String start = null;
for (Map.Entry<String,String> entry: dataSet.entrySet())
{
if (!reverseMap.containsKey(entry.getKey()))
{
start = entry.getKey();
break;
}
}
if (start == null)
{
System.out.println("Invalid Input");
return;
}
String to = dataSet.get(start);
while (to != null)
{
System.out.print(start + "->" + to + ", ");
start = to;
to = dataSet.get(to);
}
}
}
|
Python3
class Solution():
def __init__(self):
pass
def printItinerary(self,d):
reverse_d = dict()
for i in d:
reverse_d[d[i]] = i
for i in reverse_d:
if reverse_d[i] not in reverse_d:
starting_pt = reverse_d[i]
break;
while(starting_pt in d):
print(starting_pt,"->",d[starting_pt],end=", ")
starting_pt = d[starting_pt]
if __name__=="__main__":
d = dict()
d["Chennai"] = "Banglore"
d["Bombay"] = "Delhi"
d["Goa"] = "Chennai"
d["Delhi"] = "Goa"
obj = Solution()
obj.printItinerary(d)
|
C#
using System;
using System.Collections.Generic;
public class printItinerary
{
public static void Main(string[] args)
{
Dictionary<string, string> dataSet = new Dictionary<string, string>();
dataSet["Chennai"] = "Banglore";
dataSet["Bombay"] = "Delhi";
dataSet["Goa"] = "Chennai";
dataSet["Delhi"] = "Goa";
printResult(dataSet);
}
private static void printResult( Dictionary<string, string> dataSet)
{
Dictionary<string, string> reverseMap = new Dictionary<string, string>();
foreach (var entry in dataSet)
reverseMap[entry.Value] = entry.Key;
string start = null;
foreach (var entry in dataSet)
{
if (!reverseMap.ContainsKey(entry.Key))
{
start = entry.Key;
break;
}
}
if (start == null)
{
Console.WriteLine("Invalid Input");
return;
}
string to = dataSet[start];
while (true)
{
Console.Write(start + "->" + to + ", ");
start = to;
if (!dataSet.ContainsKey(to))
break;
to = dataSet[to];
}
}
}
|
Javascript
function printItinerary(dataSet)
{
let reversemap = new Map();
for (const[key,value] of dataSet)
reversemap.set(value,key);
let start = "";
for (const key of dataSet.keys())
{
if (!reversemap.has(key))
{
start = key;
break;
}
}
if (start.length == 0)
{
console.log("Invalid Input");
return;
}
let it = start;
while (dataSet.has(it))
{
console.log(it+"->"+dataSet.get(it));
it = dataSet.get(it);
}
}
let dataSet = new Map();
dataSet.set("Chennai","Banglore");
dataSet.set("Bombay","Delhi");
dataSet.set("Goa","Chennai");
dataSet.set("Delhi","Goa");
printItinerary(dataSet);
|
Output
Bombay->Delhi, Delhi->Goa, Goa->Chennai, Chennai->Banglore,
Time Complexity: O(n).
Auxiliary Space: O(n), The extra space is used in map.
Please Login to comment...