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

**** Best Books For Data Structures & Algorithms for Interviews:**********
*****************************************************************************

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

[KnowledgeCenter]

Java Code: (Thanks @Srikant Sharma for sharing):

class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
List<List<int[]>> 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<int[]> 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 <= K) {
//add adjacent nodes.
for (int[] adjNode : graph.get(city))
minHeap.add(new int[]{adjNode[0], distance + 1, cost + adjNode[1]});
}
}
return -1;
}
}

[ritikrao]

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

[manavneekhra]

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

[anantripathi]

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

[manpreetkhokhar]

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

[nagarjunvinukonda]

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

[jayaprakashreddythokala]

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

[jasmindersikka]

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

[bhavuks]

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

[harshagarwal]

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

[ChristianESL]

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

[JohnTosun]

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

[nitinnanda]

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

[indiasuhail]

Atleast the python code fails on leetcode. Timeout error.

[khorshedalam]

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?

[priyakolluru]

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?