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
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.
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; }
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 ?
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.
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"]]
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.
Can you please check your playlists once, so many videos are repetitive. Check DP videos - Perfect squares, coin change 2. Please organize the playlists.
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
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)
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.
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.
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"]
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 ..
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.
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.
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...
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.
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.
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.
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.
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!
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
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 :)
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 :)
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);
}
Mad respect for you bro, the way you broke down the problem and simplified it
Thanks 😊
Love the thought process when using a stack
😀
Thanks for explaining. It helps immensely if you can also talk about intuition behind why the chosen logic would work. Cheers!
This video was so helpful! It totally cleared up adjacency lists and stacks for me.
Thank you!
Nice ☺️
This solution is Brutally AWESOME!!!
he makes every problem so simple
I injected your technical dose in my brain (techdose) . this feels amazingggggggggg....
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 :)
You are literally god
😅
Extremely well explained
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 ?
Great Explanation
Sep'14, 2023 06:39 pm
Can't be great anymore, genius!
😁
Wow , learned new things in video thanks
Great Explanation
@Techdose explanations are awesome
Best explanation !!!
Very helpful explanation. Thanks for even covering the edge cases 👍
Welcome
Thanks a lot for your videos, mate. They're very helpful.
Welcome :)
what a nice explanation
if you are feel akward using multiset then just use priority queue
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);
}
};
👍
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 nicely explained. thanks a ton!
Welcome :)
Such a brilliant explanation ☺️😊.. thank you sir..
Welcome
Using that stack was , just 💥
:)
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
absolutely amazing explanation!!
Thanks
Very beautiful explanation.
Thanks
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.
How did you land on the thought that stack would give the right answer?
such a well and clear approach..nice
Thanks
Awesome explanation brother ❤
Awesome !!!
how you thought of stack🤔
btw great explanation🙏🙏
Brilliant
Thanks
We can solve this question without explicitly using stack through DFS. Recursion basically is implemented here with a stack.
Nice
Thanks for explanation. Can you let me know the software used in making the screens and video
I don't think interviewers will let you use the multiset Guava library in the interviews :/
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.
Iam getting TLE with this approach
can you explain why we choose the adjacency list instead of the adjacency matrix and how we can think of using stack?
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
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
so its a topological sort using dfs?
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.
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
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 :(
Code Link : techdose.co.in/reconstruct-itinerary-leetcode-332/
Smart Guy
How did u arrive at conclusion to use a stack ?
EYE TEA NERR E ( British. ) -> For fellow coders who might find it difficult to pronounce
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)
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)
👍
I have a doubt brother ,why multiset and not set? any test case for the explanation??..P.s: Your videos are great.
Correct
Nice one
Thanks :)
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.
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.
what's the intuition behind this logic?
What is the intuition behind taking stack DS
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.. 😄
Similar to leetcode course schedule ii
:)
Intuition behind using stack, is not explained properly :(
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.
cant topological sort be used?
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.
topo sort, it is
How to get the intuition of using set?
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.
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.
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.
I completely lost you on that stack part. You didnt explain the intuition behind it.
Sir, you github link is not working
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.
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.
to select the starting location!!!!!!!?
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]
😀
😁
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.
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
How do you decide that your source will be JFK?
I dont think you can generalize this.
Waiting for your video bhaiya 😅
Nice :)