Cheapest Flights Within K Stops | DFS + Pruning | Leetcode
ฝัง
- เผยแพร่เมื่อ 7 ก.ย. 2024
- This video explains a very important graph programming interview problem which is to find the minimum cost path from source to destination.This is a very typical shortest path problem and can be solved by using a variety of algorithms like Dijkstra, Floyd Warshall, Bellman Ford, BFS, DFS with memoization or pruning.In this question, we are allowed to have a maximum of K number of stops from source to destination.This is the only additional constraint.I have shown the simplest approach to solve this problem which is by using DFS + Pruning.I have first explained the intuition and then i have shown the working of the algorithm by taking an example.At the end of the video,i have also shown the code walk through. 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...
=================================================================
CODE LINK: gist.github.co...
SIMILAR PROBLEMs:-
DFS: • Depth first search | D...
BFS: • Breadth first search |...
How this solution is going to take just O(n + e) time even in the worst case? Can you explain?
I forgot to mention that time depends on your sparsity of graph. For dense graph, for finding just 1 path, time is O(V+E) but for sparse graph you can find all paths in the same amortized time. For dense graph, for finding all possible paths, you will have O(V.(V+E)) which can go to V^3 because E=V^2 for dense graph. So, the time for this problem will range from O(N+E) to O(N.(N+E)). This totally got out of mind while explaining. Thanks for this question :)
@@techdose4u what if we have a complete graph in which all paths from src to dest is at most k stops away, thus DFS is not going to prune on (k < -1), as this condition, would never hit and DFS is also not going to prune on condition (currPrice > minFare) as somehow say, we are getting the minFare cost in decreasing order, thus we are actually going to every single path from src to dst?
It can't have all paths in decreasing order in a dense graph. Now pruning depends on when you find a path with lower cost. If graph has a special configuration so that your DFS algo (depending on how you made adjacency list) do not prune, then this can only happen when all paths leading to dst are within K stops and all the paths in our DFS are coming in decreasing order of totCost. But this test case will be rare. Also, I mentioned before explaining that this is one of the slowest method (even though it's VE but still it's recursion and not loop).The only optimization is pruning. This works fine if the test case is not designed to make this technique fail. If time complexity is more stringent then try other optimal methods using dynamic programming.
@@techdose4u Got it. Thanks!
👍
I am having TechDose regularly as suggested by my frnd and its really making me more efficient coder.
Nice :)
Good work, We want more solution like this: Simple Method+ Pruning , I Learned a New things ,Thank you
Keep learning :)
He sets visited[src] = true so that while exploring some node, you don't visit it again. That can happen if there exist cycle in the graph. But setting it again to false after for loop so that that node can be visited in some other path as he explained in some reply.
Actually here you can even avoid usage of visited array. Not using visited array in dfs will give you all different paths from source node to any other node. ALL DISTINCT PATH!! As you are pruning here by two constraints that are 1- k(at most k stops) and 2- smaller cost. You will get all the paths that are in bound of these two constraints. And we want one of them that is having smallest cost.
Hope it helps. @TECH DOSE please correct me if I am wrong anywhere.
Keep it up!! TECH DOSE, you are helping a lot of people!
I solved it using BFS with the help of heap. Really interesting problem. Thanks for the alternate solution using dfs!
Can tell me the full algorithm technique?
Did you store the cost of every possible s to d path within 'k' stops in a min-heap and then just returned the 1st element/root of the heap???
TECH DOSE, please make a video on other ways of doing this problem, will help a lot!! Also in many interviews they ask to solve the same problem but with different approaches.
Yea right.
This method is giving TLE in leetcode
Always makes problem more simple and solve with efficient solution ! Good work :p
Thanks :)
@@techdose4u bro .pb is not working
@@techdose4u why you have used that by the way
thank you sir for so awesome content.i just want to make one request to you that please try to make solution videos using other approaches also like dijkstra algo etc.This will help our mind to evolve and we can think of many solutions to a problem whenever interviewer asks us tell approach to solve the questions.once again thank you for doing so much hard work for all of us.
Yea sure...I am trying to do this.
Iam getting TLE with the above mentioned approach
Try to optimize with priority queue code
Thanks for teaching a new concept Pruning with dfs.
thank you very much sir awesome content ! i actually wanted to see dijkstra's algo approach as well.. if you have some time please make this solution based on dijkstra algo as well.. ❤❤❤
Yea sure. I will explain graph as well :)
The same method I came up with in C#. In large test cases TLE comes.
A small optimization which we can make in the given code acc to me. I think on line 16 we can replace
This approach is giving TLE
Optimize by using heap
Awesome explanation. Bdw rap starts at 18:19. Thank me later :D
😅
hahahaha
Content is very useful, I appreciated! WARNING RUBBISH ADS: { Actually I got some ads like: " In order to take my girlfriend on dinner so I started " , bhai etna bhauk kyo ho rha toda sabar kar le dimag mat kharab kar.}
Are we trying to explore every possible path in this solution and making optimization by not making further calls in case the number of stops surpasses k or cost of current path becomes more than minCost .
Nice explanation , but this solutions give TLE on leetcode. Only bellman ford shall pass on leetcode
Optimize the code
I think the test cases for this problem were not very exhaustive. You can see accepted answer in python and I think it does not even implement several optimizations and checks for test cases but it still passed.
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
answer = 10**9
from_city = {}
for source, destination, price in flights:
if source in from_city:
from_city[source][destination] = price
else:
from_city[source] = {destination: price}
stack = [(src,0, K)]
while stack:
start, cost, steps = stack.pop()
if start!=dst:
steps-=1
else:
answer = min(answer,cost)
pass
if steps>-2 and answer>cost and start in from_city:
for destination in from_city[start]:
price = from_city[start][destination]
stack = [(destination, cost+price, steps)]+stack
return answer if answer!=10**9 else -1
Yes I think that too. But just enjoy the accepted code for now :P
You explained very clearly,by the way i follow you channel,you really explain things very clearly,even the tough questions.But your solution is getiing tle on leetcode for this problem.
Use priority queue in implementation
Thanks for the very clear explanation and listing all the possible ways to do it.
For the DFS + Prunning method, even if we are using a visited array, how is the time complexity still the worst among all other techniques?
class Solution {
public:
void solve(int n,vectoradj[],int k,int src,int dst, vector&vis,int &ans,int cost){
if(k
Please make video on graph with some questions
Why are you using this line of code ?
if prices[s] == float("inf"): continue
is it necessary since you initialize prices[src] = 0 in the begin so in my understanding it can't be infinite again
Waiting for this!!!!
Solved it?
@@techdose4u Not yet!
47 / 49 test cases passed. if I use DFS + Pruning.
Optimize the code as per new TCs
HI Tech dose i guess pruning will not work with negative weight
if we are returning from a particular node just because of value is greater then total max and on next node there is negative value then pruning will fail.
Not only with this problem but in general graph where positive and negative value present.
How we can solve this using Dijkstra with the constraint of 'K' stops. It's a greedy method, will it work here ? If there is no constraint for 'K' stops, then it would work for sure!
I got TLE when I recently tried.
me too
I think leetcode expect us to solve using DP
please make a video on operations on vector of vector (especially for comparators for vector of vector)
👍
Bro please explain all the 6 approach you've listed
I will explain all in future but explaining them without a reference video is not possible now.
@@techdose4u sure bro... Thanks
Do You use backtracking in your DFS? That is really a Smart thinking.
Thank you sir!!
How can the time complexity id O(n+e) , you are trying all possible paths with pruning optimization and we are visiting the same vertex again in some different path?it seems time complexity will be more than O(n+e)
Awesome explanation...thnx a lot.
If DFS explores the longer path first, then pruning will not help. So it should be BFS + pruning as we will encounter the shorter path to destination and later when we explore the longer path, we can use pruning. Can someone please explain???
Grt explanation. I solved it using the same way. I know dijikstras but how can we do it when there is parameter k using dijikstras algorithm
Sir this code is giving TLE
Please optimize the code with priority queue. I have written the bruteforce approach
great explananation
Thanks :)
@TECHDOSE Great Video Sir, can u please explain why are we making vis[src]=false; again after the recursive calls.
Thanks in advance :).
We dont want to fall in a loop. So whenever we are processing a node, we don't want to travel to that node again while finding mincost from src to day and so we keep making each node true. Now as we return in our recursion, we will have to make it false so that the node can get included in some other path. This is just like cycle finding algorithm, where we make a node true and enter and while returning we make it false.
@@techdose4u got it thanks
Thanks for solution
Pls also add solution using djikstra as i feel djikstra wont work here.
I haven't tried Dijkstra. May be we need to modify something there.
why we are taking visited array ?
suppose if src=0 ,dst =3
1 path -> 0->1->2->3 and suppose 1->2 cost is 500 and u made 2 visited
2 path -> 0->2->3 and suppose 0->2 cost is 100 but u made 2 visited so we cant go there but it will be minimum cost path
Please explain?
Sir this solution is giving tle .please check it
Time Limit Exceeded in case of n = 100,
Great explanation!! But did you use prunning in your code.. Like when (totalcost>fare) return;?
Yes. Inside the for loop in solve, I have checked for totCost > fare.
sir how to do this question using dijkstra since there is a constraint of k?
Dint try it yet. But you cannot solve it using MST algos.
Why does Cost matrix in the code you have provided has the dimensions (n+1,n+1) and not (n,n)?
I'm getting TLE in leetcode for this approach! :(
Same
For n=100
Hi,
The same question can be solved using Bellman Ford or dijkstra algorithm, If possible please update on the same, or create a new video, As I was checking some other solution and these two seems to be efficient than dfs.
Not sure though but Bellman Ford uses concept of dp also.
can u please explain this question using dijkstra's algo.
47/49 test cases passed in leetcode using DFS approach. But I know the intension of the vedio was to learn DFS + pruning.
New TCs added. Please optimize the code
@@techdose4u i dont think any optimisation left in this approach,if u know pls tell us how to make it work for last few test cases on leetcode. it's failing in last 4 TCs .
Code Link : techdose.co.in/cheapest-flights-within-k-stops-dfs-pruning-leetcode-787/
Nice video but you said that the time complexity of your algorithm is O(V+E) but I think it is O(V^V). Could you please explain or correct me if I am wrong?
Please read the pinned comment.
Nicely explained thanks, can u please tell me , why did u write this : visited [src]=false at the end??
This is just the same concept for cycle finding algo in graph. First mark a node visited and then explore. While returning back from the node, mark it as unvisited so that it can be explored in some other path as well.
He sets visited[src] = true so that while exploring some node, you don't visit it again. That can happen if there exist cycle in the graph. But setting it again to false after for loop so that that node can be visited in some other path as he explained.
Actually here you can even avoid usage of visited array. Not using visited array in dfs will give you all different paths from source node to any other node. ALL DISTINCT PATH!! As you are pruning here by two constraints that are 1- k(at most k stops) and 2- smaller cost. You will get all the paths that are in bound of these two constraints. And we want one of them that is having smallest cost.
Hope it helps. @TECH DOSE please correct me if I am wrong anywhere.
Keep it up!! TECH DOSE, you are helping a lot of people!
why did you take the cost matrix size n+1?
Bro, Do you mouse to write on the black board ?? if any specific app can you tell so that I can use that to explain in my interviews ?
This solution is getting TLE
Test cases are updated. Do some optimization on my code :)
Can anyone post java code with same prototype/algorithm
Ahh, awesome trick. I was trying to implement dfs with memoization for a long time and felt going in wrong direction unless saw your trick. Can u help me with memoization approach as well? Thanks in advance.
Paste your code in comment or share the gist link. You can get help.
@@techdose4u
Here is the code.. Its getting TLE
class Solution {
int INF = 0x3F3F3F3F;
Map memo = new HashMap();
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
Map[] graph = new HashMap[n];
for(int i = 0; i < n; i++)
graph[i] = new HashMap();
for(int[] f : flights) {
graph[f[0]].put(f[1], f[2]);
}
int ans = findMinimumCostPath(graph, src, dst, -1, K);
return ans == INF ? -1 : ans;
}
int findMinimumCostPath(Map[] graph,
int src, int dst, int stop, int maxStop){
if(src == dst)
return 0;
int minCost = INF;
String key = src + "-" + dst;
for(Map.Entry entry : graph[src].entrySet()){
if(stop < maxStop)
minCost = Math.min(minCost, entry.getValue() +
findMinimumCostPath(graph, entry.getKey(), dst, stop + 1, maxStop));
}
memo.put(key, minCost);
return memo.get(key);
}
}
@@siddharthkumar2761 Were u able to get memoization working ?
With DFS+pruning but without memoization it runs into TLE
Why is dfs with pruning less efficient than BFS?
Not less efficient. If you use BFS in combination with other DS then BFS will be more efficient.
Why this seems so similar to travelling salesman problem without this pruning? Or is it only me ?
great
Hello sir based on the problem's explanation I have got a hunch about solving this problem using knapsack. Correct me if I am wrong
No not knapsack. Just single source shortest path.
@@techdose4u ok thank you
👍
Sir, can't we apply union find kruskal algo for min weight path
That can also work because finding minimum cost spanning tree will also lead to min cost path. But they should be in the same component. I guess that's why you want to use union find.
Yes, but I thought of it and I think kruskal won't work coz the spanning tree could be from the left subtree of source to the right or any other subtree of the source, that ain't the path from source to destination we want
I thought about it and concluded that MST algos won't work because of K stop condition 😅
Yeah, me too, actually I didn't even see the problem and I committed about MST but then I knew the problem
very nice!
Thanks
Cost(1,2) = 200? In the question, it is not 100?
done it with same approach giving TLE on test 37.
Here is my code :
class Solution {
void solve(vector adj, int src ,int dst, int k,int &fare,int totalCost,vector vis){
if (k
In the code pass the adjacency list and the visited array by refernce , that is being copied a lot of times and thus giving tle
please tell me algorithms which are important to master graphs
Please follow my graph playlist. I am making the important algos only.
@@techdose4u yes i am following this playlist & thank you for these awesome videos.i love the way you explain.
awesome solution !! btw what software do you use to draw on the screen? can you please share the name
Can we find shortest path in a weighted graph with this approach?
The graph you saw is weighted. Recursion is always slower as compared to loops even for same number of observable operations. So go with Dijkstra. But DFS will always work but it won't be efficient.
yes we can but its too costly , Use djikstras or bellman ford to reduce the tc
Although you have explained the pruning method still you have not used that in the code. Your solution is good but not optimized.
Can I use this solution in interviews??
thanks
Welcome
it is giving TLE in leetcode .
can you make a video on memoization ?
Dijkstra won't work! u won't be able to store in the way the question asks!
The solution not passing leet code tests and giving TLE. Please own what you publish on you tube.
its giving me TLE on 49th testcase out of 51
question link dala karo bhai.
You can search using leetcode number. Name is also mentioned :)
This solution is giving tle :(
Please optimize using heap for dijkstra
sir, pls write the code in JAVA also..
Not passing on Leetcode