Hey neetcode! Today I got intern offer from one of the FAANG companies. All credits to you for introducing me leetcode and easy python solutions. That really helped me in interviews. Thank you so much.
But I dont think u were able to solve the mysteries between the knot and the two worlds without Claudia Tiedimann ! Give a thanks to her too :-) ... Iykyk 😂
I think my study plan is to go through your list of videos and see which problems scare me, and tick them off one by one. because it's so relaxing to know that you have a solution.
There's no way in hell I would've been able to solve this in an interview. I think it's LC hard. Not only it's an advanced graph algorithm but also it's a variation of bellman ford.
Awesome explanation. For my understanding it was easier when I named "prices" "prevStepPrices" and "tempPrices" "currentStepPrices", that way it's clear why we're using a temp variable.
bro literally taught bellman ford algorithm in one short video. Respect. I was struggling so much with Djikstra's algorithm, because there's so many things to keep track of and it is fucking stupid. But bellman ford is super straightforward. Definitely gonna memorise and show off in interview, once again xD
Explanation for 'k+1' : if k stops are allowed , then only vertices that are of use are 'k' + 'src' + 'dst' == k+2 , therefore maximum routes to dst can be (k+2)-1.
Dijkstra is normally pronounced Dyke-struh, in IPA /ˈdɑɪkstɹə/. It is a Dutch name, where the 'j' is always silent or pronounced like a 'y'. So the name should be 'dyk (bike, hike in English) -stra'.
For those that are confused, I suggest watching other videos that explain Bellman-Ford in isolation. The explanation in this video is not clear at all.
One easy way to make it more efficient is to check if there is an improvement between iterations, and break out of the loop if there isn't. So replacing line 14 for: if prices != tmpPrices: prices = tmpPrices else: break
Do let me know if I am correct here. The explanation is that Bellman Ford converges with |V|-1 tries because it gets to traverse all the routes including the route that has |V|-2 vertices between vertices at two extremes is the graph. So, with K vertices in between, we run K+1 passes.
This is a very simple example, you could have picked one with cycles... Also the time complexity would be O ( k * (V+E) ) . The extra V is due to the copy of temp.
Thanks for another great video!! Idk why but I somehow find the general DFS solution easier to understand & implement. The DFS solution is like any other graph search problem, but yes it's much bulkier than this algorithm.
My conclusion is that they really want you to use Bellman-Ford for this problem. Some hints are that it gives you the number of nodes n and the list of edges. If use DFS you don't need n and you have to generate an adjacency list. The question is really built around B-F.
So I was able to modify Djisktra's algorithm, there were a couple of things that i had to do in order to get this to work: 1. PQ based on steps (nodes inbetween) 2. Allow reconsidering of visited nodes, so that we can update the values if and only if, the weights were smaller
Unfortunately, I just don’t understand how applying the Bellman Ford algorithm, magically solves the problem. If there’s someone who can explain why it works, it’d be very helpful.
This solution looks a lot like a 2D dynamic programming bottom-up approach, with the additional optimization in memory (because you only need the current and the previous value of k). I think this view of the problem might help others to understand it more easily, bc we can ignore all the relationship with bellmanford algo.
@NeetCode in the example we are comparing prices from the original array but incode we are comparing tmpprices the whole point of tmp is not to compare with it. So the code must not work how does it work?
quick question -- at 11:30 to 11:50 when evaluating whether the price of B should be updated, would it make more sense in your drawing to look at B's price in the temp table, since in more complex graphs there could be multiple potential updates to B when looking at the next 'layer' of BFS and we want to ensure we're saving the minimum price?
If we visited the edges in this order: B-C, A-B, A-C, then we would enter the first if condition for B-C, and C's price won't be updated, but that's ok, because B is not the root source so this edge doesn't fall under the first layer, so this distance doesn't matter in the first run. All edges in the first layer which are the ones directly outgoing from root source A would be updated and that's what we want
If there were edges A-D and D-C with weights 50 and 50 respectively, that's where comparing against tmpPrices array in the same run will come into play. tmpPrices[C] would be reupdated from 200 to 100
Instead of quoting bellman ford right away, I would use dynamic programming. We would store a table which will be V by (k+1). For the 0th stop, we would only explore the neighbors to the source. For the 1st stop, we would look at all the vertices that have been explored and try to check if the distance their plus the distance to neighbors would improve the current distances. We would only take the last row as the final solution. However, to save space, we could only keep two arrays of length V at a time. I was hoping this solution could be a good way for people who haven’t looked at Bellman ford’s algorithm. However, this would need an adjacency list that is easily searchable which adds extra machinery.
Hi Neet! Very nice solution you have there! I tried to DP this problem but got a timeout and I don't know how to add cache to it ! Can you help me with it ! Thanks a lot!
We are using the temp array to limit it to K stops , In Network delay time there was no such limit, we just needed the worst of the best ways to reach all nodes
However, Here we need to stop only K times in the middle, if you want to do it using Dijkstra you can probably do it but you have to pass the three infos to the queue everytime
Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman-Ford algorithm simply relaxes all the edges and does this {|V|-1}∣V∣−1 times, where |V|∣V∣ is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually, all vertices will have their correct distances. This method allows the Bellman-Ford algorithm to be applied to a wider class of inputs than Dijkstra.
``` for i in range(k) -> temp = prices.copy() for s, d, p in flights -> temp[d] = min(price[s] + p, price[d]) prices = temp return temp[dst] ``` I think we dont need to check if price[s] is infinity or not,
it is BFS because of the starting index is 0 and because of that it will only update its neighbors in 1 iteration (i.e. 1 layer of BFS) ??. otherwise i dont understand why it is bfs if lets say edges are random and not so conveniently ordered
I bet you haven't seen this unique and easy dfs approach with dp included. I bet you'll find the code easy and clean with necessary comments. Check this out: leetcode.com/problems/parallel-courses-iii/solutions/5609020/graph-dp-recursion-memoization-easy-unique-dp-approach-self-explanatory-code/
Why Multi Source BFS wont work for this problem. Coded it, but is failing 43rd testcase. Can anyone know what it is failing ? Attached code for reference: class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = {} for c1, c2, p in flights: if c1 not in graph: graph[c1] = [(c2, p)] else: graph[c1].append((c2, p))
for i in range(n): if i not in graph: graph[i] = [] res = float('inf') queue = deque() queue.append((src, 0)) visited = {src,} while queue: if k == -1: if res == float('inf'): return -1 return res queueLen = len(queue) while queueLen: city, price = queue.popleft() for nextC, nextP in graph[city]: if nextC in visited: continue if nextC != dst: queue.append((nextC, price + nextP)) visited.add(nextC) else: res = min(res, price + nextP) queueLen -= 1 k -= 1
Do we really need the continue block? Assume if prices[s] is infinity, its anyway not going to be less than tmpPrices[d] even when its value is infinity.
Just put `n_stops` as an item within the element you insert into the `min_heap` and track that. Feels much more simple than the Bellman-Ford shenanigans since we don't have any negative weights. ```python class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: adjacency_map = defaultdict(set) for vertex, subvertex, weight in flights: adjacency_map[vertex].add((subvertex, weight)) h = [(0, -1, src)] # weight, n_steps, vertex vertex2steps = {} while h: accumulated_weight, n_steps, vertex = heapq.heappop(h) if n_steps > k or n_steps > vertex2steps.get(vertex, float("inf")): continue vertex2steps[vertex] = n_steps if vertex == dst: return accumulated_weight for subvertex, weight in adjacency_map[vertex]: element = (accumulated_weight + weight, n_steps + 1, subvertex) heapq.heappush(h, element) return -1 # O(E * log E) O(E) ```
Great Video!!! I wanted to know, which kind of algorithm method is this? Is this DP? I am new to graphs and competitive coding in general, please do let me know, thanks!
With the help of this solution I made the BFS solution: class Solution: def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int: adj = {i:[] for i in range(n)} deq = deque([(0,src)]) prices = [float('inf')] * n prices[src] = 0 for cur, to, price in flights: adj[cur].append((price,to)) for i in range(k+1): for j in range(len(deq)): cost, node = deq.popleft() for price, to in adj[node]: new_cost = cost+price if prices[to] > new_cost: prices[to] = new_cost deq.append((new_cost,to))
return prices[dst] if prices[dst] != float('inf') else -1
simply because think like that: K = 1 is given. Between A -> B check will be our first iteration but when we reach B it will be 0 stop in between them right. That's why we're adding 1 to K to eliminate this problem during the problem
This code fails in leetcode due to the if condition leading to continue, here is a working implementation of above explanation class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: price = [float('inf')]*n price[src]=0 for i in range(k+1): temp = price.copy() for s,d,p in flights: temp[d] = min(temp[d],price[s]+p) price = temp if(price[dst]==float('inf')): return -1 return price[dst]
Let's create a demo graph to visualize the flight connections and better understand how the algorithm works with the given example. ### Flight Graph: We are given the following flights: - Flight from city 0 to city 1 with a cost of 100. - Flight from city 1 to city 2 with a cost of 100. - Flight from city 2 to city 3 with a cost of 100. - Flight from city 0 to city 2 with a cost of 500. Here’s how the flight graph looks visually: City 0 ------> City 1 ------> City 2 ------> City 3 | | |--------------------------------------| Cost: 500 Cost: 100 Cost: 100 Cost: 100 - Cities 0, 1, 2, and 3 are connected by flights with specific costs. - The solid lines represent direct flights between the cities, with the cost labeled along the arrows. ### Key: - City 0: Source city (starting point). - City 3: Destination city (target). - We are allowed to make at most 1 stop on our way to the destination. ### Algorithm Execution (Step-by-Step): Now, let's go through the algorithm step-by-step based on the given code. ### Step 1: Initialize the prices vector - We initialize the prices array to hold the minimum cost to reach each city. Initially, it looks like this:
prices = [0, ∞, ∞, ∞]
- 0 is the cost to reach the source city (city 0), as we're already there. - ∞ (infinity) means we haven't calculated the price for cities 1, 2, and 3 yet. ### Step 2: Iterate over Stops (Outer Loop) We will iterate k + 1 = 2 times, meaning the algorithm will consider: 1. Direct flights (0 stops). 2. Flights with 1 stop. #### Iteration 1: Checking direct flights (0 stops) - We make a copy of the prices array to tmpPrices, which will hold the updated prices for this iteration.
tmpPrices = prices;
- Now, we go through each flight in the flights list:
Flight 1: [0, 1, 100] - The flight goes from city 0 to city 1 with a price of 100. - The cost to reach city 0 is 0, so:
prices[0] + 100 = 0 + 100 = 100
- This is cheaper than the current cost for city 1 (which is ∞), so we update tmpPrices[1]:
tmpPrices[1] = 100
Flight 2: [1, 2, 100] - The flight goes from city 1 to city 2 with a price of 100. - Since we haven't reached city 1 yet (cost is still ∞), we skip this flight for now.
Flight 3: [2, 3, 100] - The flight goes from city 2 to city 3 with a price of 100. - We haven't reached city 2 yet (cost is still ∞), so we skip this flight as well.
Flight 4: [0, 2, 500] - The flight goes directly from city 0 to city 2 with a price of 500. - The cost to reach city 0 is 0, so:
prices[0] + 500 = 0 + 500 = 500
- This is cheaper than the current cost for city 2 (which is ∞), so we update tmpPrices[2]:
tmpPrices[2] = 500
- After processing all flights in the first iteration, the updated prices array is:
prices = [0, 100, 500, ∞]
#### Iteration 2: Checking flights with 1 stop - We make another copy of the prices array to tmpPrices for this iteration:
tmpPrices = prices;
- Now, we go through the flights again: Flight 1: [0, 1, 100] - The flight goes from city 0 to city 1 with a price of 100. - The cost to reach city 0 is 0, so:
prices[0] + 100 = 0 + 100 = 100
- The price to reach city 1 is already 100, so no update is needed.
Flight 2: [1, 2, 100] - The flight goes from city 1 to city 2 with a price of 100. - The cost to reach city 1 is 100, so:
prices[1] + 100 = 100 + 100 = 200
- This is cheaper than the current cost for city 2 (which is 500), so we update tmpPrices[2]:
tmpPrices[2] = 200
Flight 3: [2, 3, 100] - The flight goes from city 2 to city 3 with a price of 100. - The cost to reach city 2 is 200, so:
prices[2] + 100 = 200 + 100 = 300
- This is cheaper than the current cost for city 3 (which is ∞), so we update tmpPrices[3]:
tmpPrices[3] = 300
Flight 4: [0, 2, 500] - The flight goes from city 0 to city 2 with a price of 500. - The price to reach city 2 is already 200, which is cheaper than 500, so no update is needed. - After processing all flights in the second iteration, the updated prices array is:
prices = [0, 100, 200, 300]
### Step 3: Return the Result - After completing the iterations, we check the cost to reach city 3:
return prices[dst] == INT_MAX ? -1 : prices[dst];
- The cost to reach city 3 is 300, so we return 300 as the result. ### Final Result: The cheapest price to travel from city 0 to city 3 with at most 1 stop is 300. --- This example shows how the algorithm explores paths by relaxing edges iteratively for each possible number of stops, eventually finding the cheapest price to reach the destination city within the allowed number of stops.
A more easy to understand solution based on Djikstra's modification. Revisit nodes where there was a possibility of shorter path even if it meant costlier one (can be done by keeping the path length in the visit hash). Since while revisiting we'd have already explored the cheapest path, we can try with with the next cheapest and so on until we find the solution. import heapq class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: adjList = {i:[] for i in range(n)} for source, destination, cost in flights: adjList[source].append((destination, cost)) # (cost, count, airport) minHeap = [(0, 0, src)] visited = {} heapq.heapify(minHeap) totalCost = 0 while len(minHeap): ele = heapq.heappop(minHeap) cost, count, node = ele[0], ele[1], ele[2] if node in visited: if visited[node]
One small question, when we are assigning prices = tmpPrices aren't the two lists actually referencing to the same data? In this way if we make any change in tmpPrices down the line inside the loop then the same will be reflected in the original array right? Doesn't this defeat the whole purpose of using a tmpPrices array?
I tried to solve this with a modified Dijkstra algorithm which gives infinite weight after number of hops is > k+1. Well it kinda works for most of the cases but some inputs breaks doesn't produce the smallest path, as expected for some problem that can be solved only by DP and you try a greedy approach. Life sucks. I'm avoiding DP since it's a hard topic and I'm not even good in other topics, so I'm saving this question for later.
1. It's not a true Bellman Ford, but a modification that supports the max k requirement. Here is a nice explanation of true Bellman Ford: ruclips.net/video/obWXjtg0L64/видео.html 2. The question can be solved with a modified BFS, which stops after k + 1 iterations and does not limit visits to a node, but does that only if it can be done more cheaply than prior visits This solution is faster than the BF solution on Leetcode: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: k += 1 # k is stops, we count legs adj = collections.defaultdict(list) for s, d, c in flights: adj[s].append((d, c)) totalCost = [math.inf] * n changes = True queue = deque([(src, 0)]) i = -1 # reaching src is not an iteration while queue and i < k: print("Iteration", i) i += 1 for j in range(len(queue)): node, cost = queue.popleft(); if cost >= totalCost[node]: print("Reached", node, "again at a higher cost", cost, "ignoring") continue print("Reached", node, "cost", cost) totalCost[node] = cost for dest, price in adj.get(node, []): newCost = cost + price if newCost < totalCost[dest]: queue.append((dest, newCost))
result = totalCost[dst] return result if result != math.inf else -1
Brute force is okay probably IRL and working to more optimal solution, a lot of medium questions need pre-optimizations to pass without time exceeded though.
Nice trick !! One question though. Using temp array is kind of deviation from Bellman Ford's right ? If it were regular Bellman Ford, and k = 0, even a single iteration would also give: 0 0 1 100 2 200 But our condition produces: 0 0 1 100 2 500
💡 GRAPH PLAYLIST: ruclips.net/video/EgI5nU9etnU/видео.html
hey neetcode please solve problems from love babbar's 450 dsa sheet as well. Rest love your explanation
Hey neetcode! Today I got intern offer from one of the FAANG companies. All credits to you for introducing me leetcode and easy python solutions. That really helped me in interviews. Thank you so much.
Hey Jonas, congrats on the offer!!! I'm glad your hard work paid off!
@@NeetCode Thanks again. never stop posting videos
Congratulations Jonas!
But I dont think u were able to solve the mysteries between the knot and the two worlds without Claudia Tiedimann ! Give a thanks to her too :-) ... Iykyk 😂
w name
This is the first time I did not understand something you taught @NeetCode
I think my study plan is to go through your list of videos and see which problems scare me, and tick them off one by one. because it's so relaxing to know that you have a solution.
Oii, 2 years down the line. Updates?
are u preparing for faang?@@louisuchihatm2556
There's no way in hell I would've been able to solve this in an interview. I think it's LC hard. Not only it's an advanced graph algorithm but also it's a variation of bellman ford.
Agree, this one is really hard.
Yeah this is very difficult
Thanks for the explanation man! You pointed out what each of the prices and temp array means and made the algorithm very intuitive
can you please further explain me why we need a temp array?
Awesome explanation. For my understanding it was easier when I named "prices" "prevStepPrices" and "tempPrices" "currentStepPrices", that way it's clear why we're using a temp variable.
This channel is so underrated, NeetCode fr the GOAT
i really like the use of temp array to limit to k stops ,regular BF doesnt take care of that
bro literally taught bellman ford algorithm in one short video. Respect. I was struggling so much with Djikstra's algorithm, because there's so many things to keep track of and it is fucking stupid. But bellman ford is super straightforward. Definitely gonna memorise and show off in interview, once again xD
Your solution is constantly the most readable and elegant one! Really appreciate all your efforts!
Thank you, I have an interview for a MAANG company next week and I feel confident with the help of your videos!
Explanation for 'k+1' : if k stops are allowed , then only vertices that are of use are 'k' + 'src' + 'dst' == k+2 , therefore maximum routes to dst can be (k+2)-1.
Dijkstra is normally pronounced Dyke-struh, in IPA /ˈdɑɪkstɹə/.
It is a Dutch name, where the 'j' is always silent or pronounced like a 'y'.
So the name should be 'dyk (bike, hike in English) -stra'.
If you ever feel useless remember there is a 'j' in Dijkstra 😑
@@wernerheisenberg9653It’s just how Dutch and some similar languages work. e.g. Virgil van Dijk. Rijkaard.
For those that are confused, I suggest watching other videos that explain Bellman-Ford in isolation. The explanation in this video is not clear at all.
forreal man it just goes too quick without really explaining.
Since there are no negative weights I chose to use Djikstras algorithm. It was nice seeing this solution too!
One easy way to make it more efficient is to check if there is an improvement between iterations, and break out of the loop if there isn't. So replacing line 14 for:
if prices != tmpPrices:
prices = tmpPrices
else:
break
Wow. That's nice of a catch.
Since the the graph does not contain negative weights, cant we use Dijkstra instead ?
Do let me know if I am correct here.
The explanation is that Bellman Ford converges with |V|-1 tries because it gets to traverse all the routes including the route that has |V|-2 vertices between vertices at two extremes is the graph. So, with K vertices in between, we run K+1 passes.
superb explanation..specially the temporary array part,thanks a lot!!!
Thanks for the neat explanation and code!
This is a very simple example, you could have picked one with cycles... Also the time complexity would be O ( k * (V+E) ) . The extra V is due to the copy of temp.
I loved your videos, pls continue posting more topics. I love the way you teach.
Just a technicality, but isn't this approach O(k*(V+E)), since we are copying the temp_cost array at each iteration?
Thanks for another great video!! Idk why but I somehow find the general DFS solution easier to understand & implement. The DFS solution is like any other graph search problem, but yes it's much bulkier than this algorithm.
Same. However one problem with a DFS is that I get a TLE with 48/51 cases on leetcode with javascript
My conclusion is that they really want you to use Bellman-Ford for this problem. Some hints are that it gives you the number of nodes n and the list of edges. If use DFS you don't need n and you have to generate an adjacency list. The question is really built around B-F.
@@halahmilksheikh good thoughts, thank you.
@@halahmilksheikh I made DFS work with memoization. But then it became more of a DP solution than vanilla DFS.
Since there are no negative costs I just use Djikstras algorithm to solve this
I figured this out first try on paper, but I kept second guessing myself and I wasn't able to solve it lol. Just gotta do more of these graph problems
So I was able to modify Djisktra's algorithm, there were a couple of things that i had to do in order to get this to work:
1. PQ based on steps (nodes inbetween)
2. Allow reconsidering of visited nodes, so that we can update the values if and only if, the weights were smaller
Great explanation, Thank you so much !❤
Mind Blowing approach, Thanks Man
Amazing explanation!
Phenomenal explanation. Thank you so much !!!
Unfortunately, I just don’t understand how applying the Bellman Ford algorithm, magically solves the problem. If there’s someone who can explain why it works, it’d be very helpful.
that's literally this entire video
This solution looks a lot like a 2D dynamic programming bottom-up approach, with the additional optimization in memory (because you only need the current and the previous value of k). I think this view of the problem might help others to understand it more easily, bc we can ignore all the relationship with bellmanford algo.
What device do you use for recoding these videos? The visuals are very helpful.
@NeetCode in the example we are comparing prices from the original array but incode we are comparing tmpprices the whole point of tmp is not to compare with it. So the code must not work how does it work?
You are just tooo tooo good thankyou!
quick question -- at 11:30 to 11:50 when evaluating whether the price of B should be updated, would it make more sense in your drawing to look at B's price in the temp table, since in more complex graphs there could be multiple potential updates to B when looking at the next 'layer' of BFS and we want to ensure we're saving the minimum price?
That's why we are checking all edges at every level
You don't need the if prices[s] == float("inf") condition. Source node will never be unreachable as defined in problem
Nice explaination.. thankyou
If we visited the edges in this order: B-C, A-B, A-C, then we would enter the first if condition for B-C, and C's price won't be updated, but that's ok, because B is not the root source so this edge doesn't fall under the first layer, so this distance doesn't matter in the first run. All edges in the first layer which are the ones directly outgoing from root source A would be updated and that's what we want
If there were edges A-D and D-C with weights 50 and 50 respectively, that's where comparing against tmpPrices array in the same run will come into play. tmpPrices[C] would be reupdated from 200 to 100
Thanks Kevin😀
Great video!
Instead of quoting bellman ford right away, I would use dynamic programming.
We would store a table which will be V by (k+1). For the 0th stop, we would only explore the neighbors to the source. For the 1st stop, we would look at all the vertices that have been explored and try to check if the distance their plus the distance to neighbors would improve the current distances. We would only take the last row as the final solution. However, to save space, we could only keep two arrays of length V at a time. I was hoping this solution could be a good way for people who haven’t looked at Bellman ford’s algorithm.
However, this would need an adjacency list that is easily searchable which adds extra machinery.
yeah i'm supposed to come up with a nobel prize winning algorithms duruing the interviews
Great solution but I love how you misspell Dijkstra into Djikstra in all your videos lmao
Hi Neet! Very nice solution you have there! I tried to DP this problem but got a timeout and I don't know how to add cache to it ! Can you help me with it ! Thanks a lot!
Sorry, I still don't understand why we need the temp copy. Why 743. Network Delay Time don't need a copy ? Can anyone explain more.
We are using the temp array to limit it to K stops , In Network delay time there was no such limit, we just needed the worst of the best ways to reach all nodes
However, Here we need to stop only K times in the middle, if you want to do it using Dijkstra you can probably do it but you have to pass the three infos to the queue everytime
Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman-Ford algorithm simply relaxes all the edges and does this {|V|-1}∣V∣−1 times, where |V|∣V∣ is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually, all vertices will have their correct distances. This method allows the Bellman-Ford algorithm to be applied to a wider class of inputs than Dijkstra.
Very good explanation
Thanks for the vid 👌
tbh solution didn't make sense.It says bellman ford but talks about BFS throughout video. Also doesn't clearly explains the intution.
Agreed. This is one of his videos which I don't really prefer to follow.
```
for i in range(k) ->
temp = prices.copy()
for s, d, p in flights ->
temp[d] = min(price[s] + p, price[d])
prices = temp
return temp[dst]
```
I think we dont need to check if price[s] is infinity or not,
Here we don't but Bellman-Ford is applied on negative edges where this is useful. I think that check comes out of the algorithm
Uhhh where in your code are you gonna return -1 then?
it is BFS because of the starting index is 0 and because of that it will only update its neighbors in 1 iteration (i.e. 1 layer of BFS) ??. otherwise i dont understand why it is bfs if lets say edges are random and not so conveniently ordered
Does anyone know why we use the `tmp` array? Other implementations of Bellman-Ford online don't use it.
Great explanation. I did it in a DFS way but don't know why it doesn't work. Maybe I'm missing some edge cases.
I bet you haven't seen this unique and easy dfs approach with dp included. I bet you'll find the code easy and clean with necessary comments. Check this out:
leetcode.com/problems/parallel-courses-iii/solutions/5609020/graph-dp-recursion-memoization-easy-unique-dp-approach-self-explanatory-code/
Why Multi Source BFS wont work for this problem. Coded it, but is failing 43rd testcase. Can anyone know what it is failing ?
Attached code for reference:
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = {}
for c1, c2, p in flights:
if c1 not in graph:
graph[c1] = [(c2, p)]
else:
graph[c1].append((c2, p))
for i in range(n):
if i not in graph:
graph[i] = []
res = float('inf')
queue = deque()
queue.append((src, 0))
visited = {src,}
while queue:
if k == -1:
if res == float('inf'):
return -1
return res
queueLen = len(queue)
while queueLen:
city, price = queue.popleft()
for nextC, nextP in graph[city]:
if nextC in visited:
continue
if nextC != dst:
queue.append((nextC, price + nextP))
visited.add(nextC)
else:
res = min(res, price + nextP)
queueLen -= 1
k -= 1
return -1 if res == float('inf') else res
Thank you so much
Temp array isn’t still clear. You rushed it too quickly.
is there a way to solve this without using the temporary distances array? how come traditional bellman-ford doesn't include this?
i want to know other questions about negative price
How did you come up with this solution ? is there any resource ? it's simple , i agree the most
Why do you need tmpPrices?
14:04
Do we really need the continue block? Assume if prices[s] is infinity, its anyway not going to be less than tmpPrices[d] even when its value is infinity.
simply awsome
thank you
Hm. I just copied your code, and then changed k=0 for the inputs, which should give -1 but instead gives 500. Help?
This question can also be resolved by SPFA algorithm. The theory is similar here, but much faster than Bellman-Ford .
Does it also mean this code should work for a scenario with at least K stops and can you specify a recursion for this?
hope one day i reach your level♥
Amazing!!!
If you were to use pure Djikstra, how would you handlel the k stops condition?
Just put `n_stops` as an item within the element you insert into the `min_heap` and track that. Feels much more simple than the Bellman-Ford shenanigans since we don't have any negative weights.
```python
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
adjacency_map = defaultdict(set)
for vertex, subvertex, weight in flights:
adjacency_map[vertex].add((subvertex, weight))
h = [(0, -1, src)] # weight, n_steps, vertex
vertex2steps = {}
while h:
accumulated_weight, n_steps, vertex = heapq.heappop(h)
if n_steps > k or n_steps > vertex2steps.get(vertex, float("inf")):
continue
vertex2steps[vertex] = n_steps
if vertex == dst:
return accumulated_weight
for subvertex, weight in adjacency_map[vertex]:
element = (accumulated_weight + weight, n_steps + 1, subvertex)
heapq.heappush(h, element)
return -1
# O(E * log E) O(E)
```
Great Video!!! I wanted to know, which kind of algorithm method is this? Is this DP? I am new to graphs and competitive coding in general, please do let me know, thanks!
Bellman ford algorithm
Yes Bellman ford algorithms is a dynamic Programming type programming type algorithm.
Like always, click the like button before I watch it.
With the help of this solution I made the BFS solution:
class Solution:
def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
adj = {i:[] for i in range(n)}
deq = deque([(0,src)])
prices = [float('inf')] * n
prices[src] = 0
for cur, to, price in flights:
adj[cur].append((price,to))
for i in range(k+1):
for j in range(len(deq)):
cost, node = deq.popleft()
for price, to in adj[node]:
new_cost = cost+price
if prices[to] > new_cost:
prices[to] = new_cost
deq.append((new_cost,to))
return prices[dst] if prices[dst] != float('inf') else -1
Hi @Neetcode, why don't we need DIjkstra's algorithm for this problem?
Can someone explain why only (k+1) iterations done for this problem?
simply because think like that: K = 1 is given. Between A -> B check will be our first iteration but when we reach B it will be 0 stop in between them right. That's why we're adding 1 to K to eliminate this problem during the problem
Neetcode is OP
Such a clean explanation! Loved it
This code fails in leetcode due to the if condition leading to continue, here is a working implementation of above explanation
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
price = [float('inf')]*n
price[src]=0
for i in range(k+1):
temp = price.copy()
for s,d,p in flights:
temp[d] = min(temp[d],price[s]+p)
price = temp
if(price[dst]==float('inf')):
return -1
return price[dst]
Let's create a demo graph to visualize the flight connections and better understand how the algorithm works with the given example.
### Flight Graph:
We are given the following flights:
- Flight from city 0 to city 1 with a cost of 100.
- Flight from city 1 to city 2 with a cost of 100.
- Flight from city 2 to city 3 with a cost of 100.
- Flight from city 0 to city 2 with a cost of 500.
Here’s how the flight graph looks visually:
City 0 ------> City 1 ------> City 2 ------> City 3
| |
|--------------------------------------|
Cost: 500
Cost: 100 Cost: 100 Cost: 100
- Cities 0, 1, 2, and 3 are connected by flights with specific costs.
- The solid lines represent direct flights between the cities, with the cost labeled along the arrows.
### Key:
- City 0: Source city (starting point).
- City 3: Destination city (target).
- We are allowed to make at most 1 stop on our way to the destination.
### Algorithm Execution (Step-by-Step):
Now, let's go through the algorithm step-by-step based on the given code.
### Step 1: Initialize the prices vector
- We initialize the prices array to hold the minimum cost to reach each city. Initially, it looks like this:
prices = [0, ∞, ∞, ∞]
- 0 is the cost to reach the source city (city 0), as we're already there.
- ∞ (infinity) means we haven't calculated the price for cities 1, 2, and 3 yet.
### Step 2: Iterate over Stops (Outer Loop)
We will iterate k + 1 = 2 times, meaning the algorithm will consider:
1. Direct flights (0 stops).
2. Flights with 1 stop.
#### Iteration 1: Checking direct flights (0 stops)
- We make a copy of the prices array to tmpPrices, which will hold the updated prices for this iteration.
tmpPrices = prices;
- Now, we go through each flight in the flights list:
Flight 1: [0, 1, 100]
- The flight goes from city 0 to city 1 with a price of 100.
- The cost to reach city 0 is 0, so:
prices[0] + 100 = 0 + 100 = 100
- This is cheaper than the current cost for city 1 (which is ∞), so we update tmpPrices[1]:
tmpPrices[1] = 100
Flight 2: [1, 2, 100]
- The flight goes from city 1 to city 2 with a price of 100.
- Since we haven't reached city 1 yet (cost is still ∞), we skip this flight for now.
Flight 3: [2, 3, 100]
- The flight goes from city 2 to city 3 with a price of 100.
- We haven't reached city 2 yet (cost is still ∞), so we skip this flight as well.
Flight 4: [0, 2, 500]
- The flight goes directly from city 0 to city 2 with a price of 500.
- The cost to reach city 0 is 0, so:
prices[0] + 500 = 0 + 500 = 500
- This is cheaper than the current cost for city 2 (which is ∞), so we update tmpPrices[2]:
tmpPrices[2] = 500
- After processing all flights in the first iteration, the updated prices array is:
prices = [0, 100, 500, ∞]
#### Iteration 2: Checking flights with 1 stop
- We make another copy of the prices array to tmpPrices for this iteration:
tmpPrices = prices;
- Now, we go through the flights again:
Flight 1: [0, 1, 100]
- The flight goes from city 0 to city 1 with a price of 100.
- The cost to reach city 0 is 0, so:
prices[0] + 100 = 0 + 100 = 100
- The price to reach city 1 is already 100, so no update is needed.
Flight 2: [1, 2, 100]
- The flight goes from city 1 to city 2 with a price of 100.
- The cost to reach city 1 is 100, so:
prices[1] + 100 = 100 + 100 = 200
- This is cheaper than the current cost for city 2 (which is 500), so we update tmpPrices[2]:
tmpPrices[2] = 200
Flight 3: [2, 3, 100]
- The flight goes from city 2 to city 3 with a price of 100.
- The cost to reach city 2 is 200, so:
prices[2] + 100 = 200 + 100 = 300
- This is cheaper than the current cost for city 3 (which is ∞), so we update tmpPrices[3]:
tmpPrices[3] = 300
Flight 4: [0, 2, 500]
- The flight goes from city 0 to city 2 with a price of 500.
- The price to reach city 2 is already 200, which is cheaper than 500, so no update is needed.
- After processing all flights in the second iteration, the updated prices array is:
prices = [0, 100, 200, 300]
### Step 3: Return the Result
- After completing the iterations, we check the cost to reach city 3:
return prices[dst] == INT_MAX ? -1 : prices[dst];
- The cost to reach city 3 is 300, so we return 300 as the result.
### Final Result:
The cheapest price to travel from city 0 to city 3 with at most 1 stop is 300.
---
This example shows how the algorithm explores paths by relaxing edges iteratively for each possible number of stops, eventually finding the cheapest price to reach the destination city within the allowed number of stops.
A more easy to understand solution based on Djikstra's modification. Revisit nodes where there was a possibility of shorter path even if it meant costlier one (can be done by keeping the path length in the visit hash). Since while revisiting we'd have already explored the cheapest path, we can try with with the next cheapest and so on until we find the solution.
import heapq
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
adjList = {i:[] for i in range(n)}
for source, destination, cost in flights:
adjList[source].append((destination, cost))
# (cost, count, airport)
minHeap = [(0, 0, src)]
visited = {}
heapq.heapify(minHeap)
totalCost = 0
while len(minHeap):
ele = heapq.heappop(minHeap)
cost, count, node = ele[0], ele[1], ele[2]
if node in visited:
if visited[node]
Here is the main idea in copy array, because in every iteration of k, we dont stop
Why wouldn't we just track the number of steps we've taken as `n_steps` and continue if `n_steps > k + 1`?
One small question, when we are assigning prices = tmpPrices aren't the two lists actually referencing to the same data? In this way if we make any change in tmpPrices down the line inside the loop then the same will be reflected in the original array right? Doesn't this defeat the whole purpose of using a tmpPrices array?
I tried to solve this with a modified Dijkstra algorithm which gives infinite weight after number of hops is > k+1. Well it kinda works for most of the cases but some inputs breaks doesn't produce the smallest path, as expected for some problem that can be solved only by DP and you try a greedy approach.
Life sucks. I'm avoiding DP since it's a hard topic and I'm not even good in other topics, so I'm saving this question for later.
brilliant.
Its just too much man, How many problems are out there, and why should I learn all this, Fuck it man
good vid, just one thing you can improve on I may suggest is don't put other RUclipsrs to shame by making such good content
not just that, the code he writes is so clear and simple to follow. it is really good to write like him in interviews.
I'm new to English and algorithm. And now I'm confused, is it dikestruh or jikestruh?
how is comment at @11:53 true?
Isn’t djikstra pronounced with a hard I like “eye”?
1. It's not a true Bellman Ford, but a modification that supports the max k requirement. Here is a nice explanation of true Bellman Ford: ruclips.net/video/obWXjtg0L64/видео.html
2. The question can be solved with a modified BFS, which stops after k + 1 iterations and does not limit visits to a node, but does that only if it can be done more cheaply than prior visits
This solution is faster than the BF solution on Leetcode:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
k += 1 # k is stops, we count legs
adj = collections.defaultdict(list)
for s, d, c in flights:
adj[s].append((d, c))
totalCost = [math.inf] * n
changes = True
queue = deque([(src, 0)])
i = -1 # reaching src is not an iteration
while queue and i < k:
print("Iteration", i)
i += 1
for j in range(len(queue)):
node, cost = queue.popleft();
if cost >= totalCost[node]:
print("Reached", node, "again at a higher cost", cost, "ignoring")
continue
print("Reached", node, "cost", cost)
totalCost[node] = cost
for dest, price in adj.get(node, []):
newCost = cost + price
if newCost < totalCost[dest]:
queue.append((dest, newCost))
result = totalCost[dst]
return result if result != math.inf else -1
it's my BFS solution. a little complicated....
var findCheapestPrice = function(n, flights, src, dst, k) {
let graph = {};
for(let i = 0; i < n; i++) {
graph[i] = [];
}
for(let [from ,to, price] of flights) {
graph[from].push([to, price]);
}
let que = [[src, 0]];
let minPrice = Infinity;
let visited = {};
while(que.length && k >= 0) {
let len = que.length;
for(let i =0; i < len; i++) {
let [currNode, currPrice] = que.shift();
for(let [nextNode, nextPrice] of graph[currNode]) {
let newPrice = currPrice + nextPrice;
if (newPrice < ( visited[nextNode] || Infinity)) {
visited[nextNode] = newPrice;
if (nextNode === dst) {
minPrice = Math.min(minPrice, newPrice);
} else {
que.push([nextNode, newPrice])
}
}
}
}
k--;
}
return minPrice === Infinity ? -1 : minPrice;
};
Do we need to consider the edge case where a direct flight between two nodes is cheaper than intermediate nodes?
Nice🎉
why we use temp array can u explain agian??
I did it another way an encountered Time Exceeded :( so came here to watch this.
Brute force is okay probably IRL and working to more optimal solution, a lot of medium questions need pre-optimizations to pass without time exceeded though.
Nice trick !! One question though. Using temp array is kind of deviation from Bellman Ford's right ? If it were regular Bellman Ford, and k = 0, even a single iteration would also give:
0 0
1 100
2 200
But our condition produces:
0 0
1 100
2 500
Yes, but this extra parameter "k" forces us to not update the original algo.
> 1:54 Djikstra
Sorry this solution makes no sense. But, it works.