Cheapest Flights Within K Stops | LeetCode 787 | C++, Java, Python

LeetCode Solutions: • LeetCode Solutions | L...
June LeetCoding Challenge: • Playlist
May LeetCoding Challenge: • Playlist
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
June LeetCoding Challenge | Problem 14 | Cheapest Flights Within K Stops | 14 June,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Cheapest Flights Within K Stops,
Cheapest Flights Within K Stops c++,
Cheapest Flights Within K Stops Java,
Cheapest Flights Within K Stops python,
Cheapest Flights Within K Stops solution,
787. Cheapest Flights Within K Stops,
dijkstra algorithm,
#Facebook #CodingInterview #LeetCode #JuneLeetCodingChallenge #Google #Amazon #ShortestPath #Dijkstra

[@ritikrao1782]

it gives TLE on leetcode
this method is not correct for larger inputs

[@manavneekhra4901]

leetcode doesn't accept this solution .they must have updated test cases.

[@manpreetkhokhar5318]

I am learning a lot from this channel. Thanks. Keep it coming.I solved it by DP method.

[@KnowledgeCenter]

Great to hear!

[@Star_Bawa9]

Can you please tell me the approach

[@anantripathi5117]

I applied your solution and it failed and gave tle i think the test cases have been updated you need to update your code too

[@xapeuuu]

Very nice and clean solution!

[@KnowledgeCenter]

Thanks!

[@xapeuuu]

@@KnowledgeCenter interesting on how in this problem, we don't update the adj matrix/list at all and keep all the results inside the priority queue ^^

[@ChristianESL]

Thanks for the video. I was able to solve with java.

[@KnowledgeCenter]

Great!

[@avishkardalvi4802]

i am getting TLE in java

[@bhavuks6554]

at 20:59 seeing 'runtime error: reference binding to null pointer of type'
I could not understand why adjacency list was fixed to a pre-allocated size (n)?

[@KnowledgeCenter]

our vector was empty, and we were trying to assign values to it using adj[idx] = ...
over the next line, while building it from flights vector.

[@bhavuks6554]

@@KnowledgeCenter Oh that makes sense, thank you for replying, your videos have been helpful in understanding the daily challenge problems on LC. Thanks again :)

[@nagarjunvinukonda162]

Leetcode few test cases don't run for this solution. It says time limit exceeded

[@jayaprakashreddythokala1760]

why r u not finalising when u pop B 8/2

[@jasmindersikka7352]

this won't work. really bad time complexity also no cycle avoidance

[@FenixFahad]

Very nice👌

[@KnowledgeCenter]

Thanks a lot

[@KnowledgeCenter]

Java Code: (Thanks @Srikant Sharma for sharing):
------------------------------------------------------
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
List graph = new ArrayList();
//creating adjacency list for source cities.
for (int i = 0; i < n; i++)
graph.add(new ArrayList());
for (int[] flight : flights) {
//source city: [destination city, source to destination cost].
graph.get(flight[0]).add(new int[]{flight[1], flight[2]});
}
//MinHeap: input format: [city, distance, cost], it compares based on cost.
PriorityQueue minHeap = new PriorityQueue((a, b) -> a[2] - b[2]);
minHeap.add(new int[]{src, 0, 0});
while (!minHeap.isEmpty()) {
int[] cur = minHeap.poll();
int city = cur[0], distance = cur[1], cost = cur[2];
if (city == dst)
return cost;
if (distance

[@khorshedalam5860]

I've confusion, while updating adjacent node, should we check it's previous cost with and cost by current node and update only if cost by current node is minimum?

[@khorshedalam5860]

got it from video explanation, same node kept multiple time with different hop number

[@indiasuhail]

Atleast the python code fails on leetcode. Timeout error.

[@sumansumann8947]

This is giving tle

[@shivanshutiwari5646]

where did you min amount??

[@Ash-fo4qs]

here priority queue is used ( min heap ), so when u take the top element from the queue--u always get the minimum element based on distance.

[@nitinnanda1865]

You mentioned Java in the video title but didn't include it in the video !!

[@skmn07]

leetcode.com/problems/cheapest-flights-within-k-stops/discuss/115541/JavaPython-Priority-Queue-Solution

[@harshagarwal9057]

Wrong Solution Again, Will get into an infinite loop in case of directed cycle...! Just because leetcode used weak test cases for this question, CZcams is filled with wrong solution....!!!!!

[@harshpeswani4187]

I think it will not get into infinite loop as the stops value is also increasing so eventually it will come out of the cycle because of less than k condition. Time complexity is the issue in this solution.

[@anandmishra8060]

why not in java?

[@KnowledgeCenter]

Took a shortcut for Shortest Path. 😀

[@srikantsharma6430]

Please find below the java solution.
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
List graph = new ArrayList();
//creating adjacency list for source cities.
for (int i = 0; i < n; i++) {
graph.add(new ArrayList());
}
for (int[] flight : flights) {
//source city: [destination city, source to destination cost].
graph.get(flight[0]).add(new int[]{flight[1], flight[2]});
}
//MinHeap: input format: [city, distance, cost], it compares based on cost.
PriorityQueue minHeap = new PriorityQueue((a, b) -> a[2] - b[2]);
minHeap.add(new int[]{src, 0, 0});
while (!minHeap.isEmpty()) {
int[] cur = minHeap.poll();
int city = cur[0], distance = cur[1], cost = cur[2];
if (city == dst) {
return cost;
}
if (distance

[@VinayKumar-pi4wm]

solution gives tle

[@JohnTosun]

Language doesnt matter but that is not a good explanation. U are mixing dijkstra and some of your thoughts

[@priyakolluru356]

Why didn't you take visited array? Neighbours of D is B and E. Where are you marking visited? If you do not need to take visited, why don't we?

[@rishirajkalita9883]

its a directed graph so u can avoid using visit array

[@idriskas]

you didnt do it in java

[@KnowledgeCenter]

Took Shortcut.

[@gaunikasrivastava7851]

Hella slow explanation

[@pulkitxd]

Painstakingly Slow Explanation