Reconstruct Itinerary | Leetcode
Vložit
- čas přidán 27. 06. 2020
- This video explains an important graph programming interview problem which is to reconstruct itinerary.This problem can be solved by using just simple graph traversal technique by using multiset and stack.Map is used to construct the adjacency list because we need random access by string value.Multiset is used to keep the values sorted in ascending order.Stack is used to handle the route exceptions.I have explained the entire problem step by step by using proper examples and intuition for each step.I have dry run the algorithm and have also explained the code walk through at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINKs:-
Representation of graph using adjacency matrix and adjacency list: • Representation of grap...
DFS: • Depth first search | D...
BFS: • Breadth first search |...
How can this be O(E)? How can the removal of edge from the adjacency list (sorted by value) be O(1)?
Insertion & Deletion is logN in a multiset.So,if you consider all the insertions and deletions, it will be O(ElogE).
Amortized complexity is O(1) and worst case complexity is O(log(size_of_ds))
Yea correct.
you can use priority queue instead of multiset .if you use priority queue then you are removed first element which is O(N)
This stack DS in this problem was really not intuitive. Good one!
Thanks
Your videos are so good! I love the way you break down problems and give such clear concise answers. Thank you so much!
Welcome :)
HI @Techdose
I am a Java developer , so most of the times , i don't understand fully your C++ code , but i liked your thought process , so whenever i stuck , i came to your channel , i am preparing for my upcoming interview . This problem seems to be tricky DFS ( Post order Traversal problem ) .
/**
[
["JFK","SFO"],
["JFK","ATL"],
["SFO","ATL"],
["ATL","JFK"],
["ATL","SFO"]
]
JFK= [SFO,ATL] , SFO=[ATL] ,ATL =[JFK,SFO]
1. Prepare the adjList = JFK= [SFO,ATL] , SFO=[ATL] ,ATL =[JFK,SFO].
2. Then do DFS for each neighbours . Only trick is do Post order where neighbours goes first and then actual Node.
3. Since the answer is in reverse Order . Then reverse at last.
NOTE : I have used PriorityQueue for maintaining sorted order in Adjacency list.
dfs
Iteration Answer
start = JFK answer [SFO,ATL,SFO,JFK, ATL,JFK]
ATL answer [SFO,ATL,SFO,JFK, ATL]
JFK answer [SFO,ATL,SFO,JFK]
SFO answer [SFO,ATL,SFO]
ATL answer [SFO,ATL]
SFO answer [SFO] --- started populating from here since it is recursion
**/
public List findItinerary(List tickets) {
List answer = new ArrayList();
if(tickets== null|| tickets.isEmpty()){
return answer;
}
Map adjList = new HashMap();
for(List ticket : tickets){
if(!adjList.containsKey(ticket.get(0))){
adjList.put(ticket.get(0),new PriorityQueue());
}
adjList.get(ticket.get(0)).offer(ticket.get(1));
}
dfs("JFK",adjList,answer);
Collections.reverse(answer);
return answer;
}
private void dfs(String node,Map adjList,List answer) {
PriorityQueue neighbours = adjList.get(node);
if(neighbours != null && !neighbours.isEmpty()){
int size = neighbours.size();
while(!neighbours.isEmpty()){
String neigh = neighbours.poll();
dfs(neigh,adjList,answer);
}
}
answer.add(node);
}
Thanks for explaining. It helps immensely if you can also talk about intuition behind why the chosen logic would work. Cheers!
Love the thought process when using a stack
😀
This video was so helpful! It totally cleared up adjacency lists and stacks for me.
Thank you!
Nice ☺️
Mad respect for you bro, the way you broke down the problem and simplified it
Thanks 😊
much better than the leetcode solution.. I attempted by using recursion and loop through adj nodes and tried to keep track of which ones ive visited but keep encountering edge case errors... learned something new with stacks today
Nice :)
This solution is Brutally AWESOME!!!
Thanks a lot for your videos, mate. They're very helpful.
Welcome :)
Great Explanation
Sep'14, 2023 06:39 pm
he makes every problem so simple
I injected your technical dose in my brain (techdose) . this feels amazingggggggggg....
Wow , learned new things in video thanks
Great explanation Thanks! The process of Adding to stack -> popping the elements -> reversing them before returning answer; instead of that can we use queue, we can reduce the cost of reversing the answer array ?
if you are feel akward using multiset then just use priority queue
Extremely well explained
what a nice explanation
Awesome !!!
Very helpful explanation. Thanks for even covering the edge cases 👍
Welcome
Best explanation !!!
You are literally god
😅
Can't be great anymore, genius!
😁
@Techdose explanations are awesome
very nicely explained. thanks a ton!
Welcome :)
so its a topological sort using dfs?
How did you land on the thought that stack would give the right answer?
absolutely amazing explanation!!
Thanks
Such a brilliant explanation ☺️😊.. thank you sir..
Welcome
such a well and clear approach..nice
Thanks
Awesome explanation brother ❤
Make July challenge videos also. It would be really helpful to learn from you!Dont stop :)
I will make graph algorithms. Lately, a lot of graph questions are coming on leetcode. It will be better to cover the basics first :)
@@techdose4u bhaiya please make graph videos . U really understands well :)
@@techdose4u If you do explain a graph algorithm, it would be great if you link an example problem on leetcode, so we can practise :)
Yea that's a great idea :)
can you explain why we choose the adjacency list instead of the adjacency matrix and how we can think of using stack?
What is the intuition behind using stack? How do we derive the idea of using a stack? Can anyone shed some light here?
It's DFS graph traversal which uses a stack
Very beautiful explanation.
Thanks
Using that stack was , just 💥
:)
Nice
Smart Guy
hi sir i need one help from you side
when i click on solution tab in leet code it shows u have to subscribe
sir is it not free, sir whether I have to pay for that ..
Some solutions on leetcode are locked.
Thanks for explanation. Can you let me know the software used in making the screens and video
Brilliant
Thanks
how you thought of stack🤔
btw great explanation🙏🙏
i did it same thing using recursion ....and also used priority queue to keep adjacency list sorted in the map .
Sir , which is better acc to you /// multiset or priority queue??
Both have the same complexity. So anything is fine.
@@techdose4u ok
please include live coding at the end of the video...your explaination are awesome but when i start to code m stuck on who to implement it.
It doesn't make sense to code again because it will take a lot of time to code and if any error comes during recording then that will be painful as well.Having already written code reduces the time of video as well. It's better to just listen to the idea and then you can have a peek at the code and then try implementing it. It should be fun. If you are stuck then have a look at the code again.
Nice one
Thanks :)
Can we use set in place of multiset?
No you cannot in this problem because there may b multiple flights from one city to anothr city
What is the intuition behind taking stack DS
Iam getting TLE with this approach
sir why u have used multiset instead of sets as we cannot have more than 1 ticket between same source and destination or can we have?? i think its not mentioned in the question that's why u have taken multiset na otherwise u would have gone with sets right??
Ho sakta hain, check this test case
[["EZE","AXA"],["TIA","ANU"],["ANU","JFK"],["JFK","ANU"],["ANU","EZE"],["TIA","ANU"],["AXA","TIA"],["TIA","JFK"],["ANU","TIA"],["JFK","TIA"]]
Cyclic route will have same destinations multiple times.
How did u arrive at conclusion to use a stack ?
We can solve this question without explicitly using stack through DFS. Recursion basically is implemented here with a stack.
but if we are using dfs then even if there is a dead end then it will get back to parent node ....why will the execution stop if dead end is there
+1
but there was no route from dead end to parent node , there was not any edge from dead end to parent , queesitons says you have travel if there is an edge
@@sidharthdhiman4522 but this can be implemented using dfs(recursive)
those who don't want to use multi set,We can sort the array in reverse order, as popping the first element is a costly operation
cant topological sort be used?
How to get the intuition of using set?
Sir plzzz make lectures in which u cover all the topics of data structures..
there are many lectures in youtube but kisi ka code nhi diya hai .... it will be really helpful if we code using your logic
I dint get your question. I think you need me to cover all DS with cod right? So, yes i will make organized lectures from July. Starting from GRAPH then DP and then rest.
@@techdose4u yes sir ... it will be helpful
I don't think interviewers will let you use the multiset Guava library in the interviews :/
topo sort, it is
Code is the gist might have an extra while loop in if condition. Please check.
Yea it was the incorrect version which I was trying. I have updated with the correct version.
I have a doubt brother ,why multiset and not set? any test case for the explanation??..P.s: Your videos are great.
Correct
EYE TEA NERR E ( British. ) -> For fellow coders who might find it difficult to pronounce
Similar to leetcode course schedule ii
:)
Great. But It would have been better if you had explained the intution behind taking the stack. You have just simply used it. But the intuition of using stack is not clear.
Code Link : techdose.co.in/reconstruct-itinerary-leetcode-332/
Can you please check your playlists once, so many videos are repetitive. Check DP videos - Perfect squares, coin change 2. Please organize the playlists.
Yes will do it. Its youtube error :(
class Solution {
public:
vector findItinerary(vector& tickets)
{
for (vectorticket : tickets)
targets[ticket[0]].insert(ticket[1]);
visit("JFK");
return vector(route.rbegin(), route.rend());
}
map targets;
vector route;
void visit(string airport)
{
while (targets[airport].size())
{
string next = *targets[airport].begin();
targets[airport].erase(targets[airport].begin());
visit(next);
}
route.push_back(airport);
}
};
👍
Please tell me why stack is helping ? i know its giving the correct answer what is intuition behind it so that in future in can think of stack if this kind of problem comes
We are doing DFS. It's tricky though. We need to take care of the condition which I showed you. We travel to a lexically smaller node but it doesn't have the return path. If you take a stack then it will be popped first and hence will be at last in our answer array. That's the idea for using stack.I showed the example in video. I got that after getting WA on the same test case.
I have the same question..
@@techdose4u i did.everything just stack part didnt came into my mind i got WA for returning component part...thankyou so much
I got stack idea from the WA which I showed in the video. Choosing the wrong path.
Hi!! thank you for your amazing lecture as always.
I'm using c++11 on vscode but for some reason multiset STL doesn't work on my environment.
Is there any way to handle with that?
Thank you!
Try some other version of CPP like CPP-17 etc.
to select the starting location!!!!!!!?
😀
😁
Sir can you please tell us that How we got to know that which data structure should be used for such problems. Because When I try this type of question by my own then it took a long time to get some observation and logic behind it...
One more thing is how much time it takes you to do this type of questions to you if it is completely new question to you ????
It depends. I got 2 WA before I submitted the correct version. Took 40 mins to solve this. It was slightly tricky. I was using map + vector. Then moved to Map+ multiset. After that I got WA and took that test case and used stack to finally get it correct. So, it was not that simple to solve at one shot because problem was not clear.
Sir, you github link is not working
Python Code :
from collections import defaultdict
matrix = defaultdict(lambda: [])
for i in tickets:
matrix[i[0]].append(i[1])
for i in matrix:
matrix[i].sort(reverse=True)
ans = []
def dfs(i):
if matrix[i]:
v = matrix[i].pop()
dfs(v)
if matrix[i]:
dfs(i)
else:
ans.append(i)
else:
ans.append(i)
dfs('JFK')
print(ans)
👍
Very well explained :)
I tried to do without stack got TLE!
class Solution {
public:
vector findItinerary(vector& tic) {
unordered_map m;
for(int i=0;i
could not understand intuition behind using stack
Stack is used for backtracking. So that when we backtrack from a path then we simply pop stack elements to get traversed nodes from fest to source order.
please provide link of this question.. on gfg.. also.. 😄..
This is from leetcode I guess
@@techdose4u yesss.., i didn't find it on.. gfg..
but thanks for your videos..! i start coding 6 November 2020.. and i score.. 650 .. in 3 months.. 😄
Waiting for your video bhaiya 😅
Nice :)
Hi Buddy , it seems like your code is only working for 18 out of 80 test cases
One such EXample is [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]] the correct out put is ["JFK","NRT","JFK","KUL"]
Updated now. That was the wrong version which I shared.
The answer is coming out wrong after submission please check the code. Only 18 out of 80 cases are getting passed
Code is fine Karan. I also used same logic
@@spetsnaz_2 idk why my test cases are getting failed. I guess i should've tweak the code a bit.
@@Karan-vq5vg Yes 18/80 cases are passing
yes, the code is partially accepted. TECH DOSE Sir please correct it!
The problem with the code is the second while statement. After you reach an edge with size = 0 you need to pop only that edge and continue with the code. The "while" there was removing every edge as soon as an edge with size == 0 was found.
You placed N sticks on a straight line. The i th stick is located at position xi and has height hi. There are no two sticks located at the same position.
You can push sticks to make them fall to the left or the right side. While falling, a stick can touch its neighbors and make them to fall in the same direction.
If a stick at position x with height h is falling to the left, then it makes all the sticks at positions (x - h)....x inclusive fall on to the left.
If a stick is falling to the right, it makes all the sticks at positions x...(x + h) inclusive to fall to the right.
Your task is to determine the minimal number of sticks you are required to push to make all N sticks fall.
ex :
5 sticks
1 2
3 1
6 2
7 1
9 2
ans : 2
note:
1 , 2 indicates a stick is placed at x = 1 with a height h = 2
Sir, can you help me with this.
Where did you get the question?
@@BarkaDog A friend of mine asked me if I can solve this.
Hi, this is an interesting question, first you will have to form 2 graphs assuming only left falls are allowed in first graph and only right falls for the second one. Then, you can find vertices with indegree zero in both graphs, these are vertices that must fall in case only left or right falls are allowed. These vertices will cover the whole distance in which all sticks are placed. Now, keeping the intervals of vertex covers for both graphs side by side, you need to choose minimum number of intervals that cover the whole distance in which the sticks are placed, this can easily be done by starting to pick interval from both ends of distances greedily by choosing larger interval from the ones having same start or end point.
I completely lost you on that stack part. You didnt explain the intuition behind it.
How do you decide that your source will be JFK?
I dont think you can generalize this.
Python recursive solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
res = ["JFK"]
tickets.sort()
adj = collections.defaultdict(list)
for src, dst in tickets:
adj[src].append(dst)
if dst not in adj:
adj[dst] = []
output = []
stack = ["JFK"]
def dfs(src):
while adj[src]:
nei = adj[src].pop(0)
stack.append(nei)
dfs(nei)
if stack:
stack.pop()
output.append(src)
dfs("JFK")
return output[::-1]