Reconstruct Itinerary | Leetcode

[@subham-raj]

How can this be O(E)? How can the removal of edge from the adjacency list (sorted by value) be O(1)?

[@techdose4u]

Insertion & Deletion is logN in a multiset.So,if you consider all the insertions and deletions, it will be O(ElogE).

[@vineetsharma4635]

Amortized complexity is O(1) and worst case complexity is O(log(size_of_ds))

[@techdose4u]

Yea correct.

[@dhruvbhanderi3407]

you can use priority queue instead of multiset .if you use priority queue then you are removed first element which is O(N)

[@parekshamanchanda8083]

This stack DS in this problem was really not intuitive. Good one!

[@techdose4u]

Thanks

[@AnshulSharma-vw9wu]

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); }

[@coreyladovsky1501]

Your videos are so good! I love the way you break down problems and give such clear concise answers. Thank you so much!

[@techdose4u]

Welcome :)

[@danielpark4204]

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

[@techdose4u]

Nice :)

[@yuhaokong]

Love the thought process when using a stack

[@techdose4u]

😀

[@maheshkumartangella5516]

Mad respect for you bro, the way you broke down the problem and simplified it

[@techdose4u]

Thanks 😊

[@SameerSrinivas]

Thanks for explaining. It helps immensely if you can also talk about intuition behind why the chosen logic would work. Cheers!

[@srikrishnarohanmadiraju8688]

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 ?

[@jlecampana]

This solution is Brutally AWESOME!!!

[@enigma2886]

he makes every problem so simple

[@b.jayanagavarmavarma191]

I injected your technical dose in my brain (techdose) . this feels amazingggggggggg....

[@sarahpark8739]

This video was so helpful! It totally cleared up adjacency lists and stacks for me. Thank you!

[@techdose4u]

Nice ☺️

[@UrGuru]

You are literally god

[@techdose4u]

😅

[@TheTushar35]

Make July challenge videos also. It would be really helpful to learn from you!Dont stop :)

[@techdose4u]

I will make graph algorithms. Lately, a lot of graph questions are coming on leetcode. It will be better to cover the basics first :)

[@nikhilshrivastava8411]

@@techdose4u bhaiya please make graph videos . U really understands well :)

[@Mauglus]

@@techdose4u If you do explain a graph algorithm, it would be great if you link an example problem on leetcode, so we can practise :)

[@techdose4u]

Yea that's a great idea :)

[@googleit2490]

Great Explanation Sep'14, 2023 06:39 pm

[@amitkumarmaity1858]

Extremely well explained

[@MuntasirHossen-w3s]

@Techdose explanations are awesome

[@devanshuLitoria]

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.

[@techdose4u]

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.

[@srisharadhars862]

How did you land on the thought that stack would give the right answer?

[@SHIVAMRANA-xn8zg]

Great Explanation

[@xingwangcheng4965]

Can't be great anymore, genius!

[@techdose4u]

😁

[@sakshid1724]

what a nice explanation

[@RahulRaj-rq4lh]

Wow , learned new things in video thanks

[@dhruvbhanderi3407]

if you are feel akward using multiset then just use priority queue

[@utsavaggrawal2697]

how you thought of stack🤔 btw great explanation🙏🙏

[@KevinN44]

Very helpful explanation. Thanks for even covering the edge cases 👍

[@techdose4u]

Welcome

[@huyphihoang7984]

can you explain why we choose the adjacency list instead of the adjacency matrix and how we can think of using stack?

[@purushottamkumar4056]

Using that stack was , just 💥

[@techdose4u]

:)

[@ksquare1112]

Thanks for explanation. Can you let me know the software used in making the screens and video

[@kunalsoni7681]

Such a brilliant explanation ☺️😊.. thank you sir..

[@techdose4u]

Welcome

[@messi_codes]

so its a topological sort using dfs?

[@arjunsabu4927]

Best explanation !!!

[@ShaliniNegi24]

Very beautiful explanation.

[@techdose4u]

Thanks

[@lokeshojha1542]

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

[@techdose4u]

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.

[@lokeshojha1542]

@@techdose4u yes sir ... it will be helpful

[@mausami16mau]

very nicely explained. thanks a ton!

[@techdose4u]

Welcome :)

[@electric336]

Thanks a lot for your videos, mate. They're very helpful.

[@techdose4u]

Welcome :)

[@Spham99]

I don't think interviewers will let you use the multiset Guava library in the interviews :/

[@sarthakgupta1263]

i did it same thing using recursion ....and also used priority queue to keep adjacency list sorted in the map .

[@sarthakgupta1263]

Sir , which is better acc to you /// multiset or priority queue??

[@techdose4u]

Both have the same complexity. So anything is fine.

[@sarthakgupta1263]

@@techdose4u ok

[@aashishkohli1198]

How did u arrive at conclusion to use a stack ?

[@ashishkempwad3267]

Can we use set in place of multiset?

[@AlanSchooll]

No you cannot in this problem because there may b multiple flights from one city to anothr city

[@SinghFlex]

I have a doubt brother ,why multiset and not set? any test case for the explanation??..P.s: Your videos are great.

[@techdose4u]

Correct

[@nishanksoni7120]

Can you please check your playlists once, so many videos are repetitive. Check DP videos - Perfect squares, coin change 2. Please organize the playlists.

[@techdose4u]

Yes will do it. Its youtube error :(

[@ShubhamMahawar_Dancer_Actor]

such a well and clear approach..nice

[@techdose4u]

Thanks

[@monishnjs]

Brilliant

[@techdose4u]

Thanks

[@harshavardhanmadasi1681]

Iam getting TLE with this approach

[@desi_boyz6165]

what's the intuition behind this logic?

[@tanujkalra7334]

absolutely amazing explanation!!

[@techdose4u]

Thanks

[@shobhitkumar6820]

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??

[@ShreyaSingh-vr9qi]

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"]]

[@techdose4u]

Cyclic route will have same destinations multiple times.

[@Vishalraj_1]

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); } };

[@techdose4u]

👍

[@muneeswaranbalasubramanian6528]

What is the intuition behind using stack? How do we derive the idea of using a stack? Can anyone shed some light here?

[@micahsimmons7520]

It's DFS graph traversal which uses a stack

[@lingasodanapalli615]

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.

[@abhishek__anand__]

Nice

[@rahulgarg7966]

please provide link of this question.. on gfg.. also.. 😄..

[@techdose4u]

This is from leetcode I guess

[@rahulgarg7966]

@@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.. 😄

[@sanjanajhawar9982]

Awesome !!!

[@manthankhorwal1477]

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

[@techdose4u]

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.

[@KaranSharmaJi]

I have the same question..

[@manthankhorwal1477]

@@techdose4u i did.everything just stack part didnt came into my mind i got WA for returning component part...thankyou so much

[@techdose4u]

I got stack idea from the WA which I showed in the video. Choosing the wrong path.

[@TomJerry-bp9ig]

Awesome explanation brother ❤

[@PatelFromPatna]

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

[@uditagrawal6603]

+1

[@sidharthdhiman4522]

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

[@Anythiny]

@@sidharthdhiman4522 but this can be implemented using dfs(recursive)

[@chixjain5800]

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)

[@techdose4u]

👍

[@UCS_RheaRaviSharma]

We can solve this question without explicitly using stack through DFS. Recursion basically is implemented here with a stack.

[@manojboganadham9071]

What is the intuition behind taking stack DS

[@rakeshmanwani4993]

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...

[@rakeshmanwani4993]

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 ????

[@techdose4u]

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.

[@shashikantkumar5095]

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

[@utkarshsharma357]

Intuition behind using stack, is not explained properly :(

[@rahulagarwal182]

Smart Guy

[@somith16]

cant topological sort be used?

[@MGtvMusic]

EYE TEA NERR E ( British. ) -> For fellow coders who might find it difficult to pronounce

[@Sky-nt1hy]

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!

[@techdose4u]

Try some other version of CPP like CPP-17 etc.

[@tanyarajhans5560]

How to get the intuition of using set?

[@AnshulSharma-vw9wu]

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"]

[@techdose4u]

Updated now. That was the wrong version which I shared.

[@MagicalCreationAviCreation]

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 ..

[@techdose4u]

Some solutions on leetcode are locked.

[@YouTube-Joy-Happy]

Nice one

[@techdose4u]

Thanks :)

[@frostcs]

Code is the gist might have an extra while loop in if condition. Please check.

[@techdose4u]

Yea it was the incorrect version which I was trying. I have updated with the correct version.

[@mahesh_kok]

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]

[@rahulvutukuri9254]

Sir, you github link is not working

[@meghasharma3092]

could not understand intuition behind using stack

[@techdose4u]

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.

[@ksTales]

Similar to leetcode course schedule ii

[@techdose4u]

:)

[@udayreddy4475]

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.

[@BarkaDog]

Where did you get the question?

[@udayreddy4475]

@@BarkaDog A friend of mine asked me if I can solve this.

[@manindersinghsaluja5802]

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.

[@paragggoyal1552]

its called topological sorting, you should explain why does the topological sort works here. rather than explaining the procedure, give the reasoning for the procedure.

[@shubhamsapra81]

topo sort, it is

[@Karan-vq5vg]

The answer is coming out wrong after submission please check the code. Only 18 out of 80 cases are getting passed

[@spetsnaz_2]

Code is fine Karan. I also used same logic

[@Karan-vq5vg]

@@spetsnaz_2 idk why my test cases are getting failed. I guess i should've tweak the code a bit.

[@nikhilshrivastava8411]

@@Karan-vq5vg Yes 18/80 cases are passing

[@AbhishekKumar-hj4qo]

yes, the code is partially accepted. TECH DOSE Sir please correct it!

[@JeanPLugo]

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.

[@nishantboro4728]

I completely lost you on that stack part. You didnt explain the intuition behind it.

[@spetsnaz_2]

Code Link : techdose.co.in/reconstruct-itinerary-leetcode-332/

[@NikhilSingh-hv9cm]

to select the starting location!!!!!!!?

[@rajatbudania6181]

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

[@bostonlights2749]

😀

[@techdose4u]

😁

[@duedares]

How do you decide that your source will be JFK? I dont think you can generalize this.

[@nikhilshrivastava8411]

Waiting for your video bhaiya 😅

[@techdose4u]

Nice :)