Cheapest Flights Within K Stops LeetCode solution in Java

1
class Solution {
2
  public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
3
    // Initialize Prices arr with infinity & src 0
4
    int[] prices = new int[n];
5
    for (int i = 0; i < n; i++) prices[i] = Integer.MAX_VALUE;
6
    prices[src] = 0;
7

8
    // Build Adj list {key: src | val: dst+price}
9
    Map<Integer, List<int[]>> flightsMap = new HashMap<>();
10
    for (int[] flight : flights) {
11
      int flightSrc = flight[0];
12
      int flightDst = flight[1];
13
      int flightPrice = flight[2];
14

15
      List<int[]> flightsList = flightsMap.getOrDefault(flightSrc, new ArrayList<>());
16
      flightsList.add(new int[] {flightDst, flightPrice});
17
      flightsMap.put(flightSrc, flightsList);
18
    }
19

20
    // Start Bellman ford Algo
21
    Queue<Integer> q = new LinkedList<>();
22
    q.offer(src);
23
    while (k >= 0 && !q.isEmpty()) {
24
      int[] tempPrices = new int[n]; // Temporary Prices Arr
25
      for (int i = 0; i < n; i++) tempPrices[i] = prices[i];
26

27
      int size = q.size();
28
      for (int i = 0; i < size; i++) {
29
        int curSrc = q.poll();
30
        int curPrice = prices[curSrc];
31
        List<int[]> curFlightsList = flightsMap.getOrDefault(curSrc, new ArrayList<>());
32
        for (int[] flight : curFlightsList) {
33
          int flightDst = flight[0];
34
          int flightPrice = flight[1];
35
          int newPrice = curPrice + flightPrice;
36
          if (newPrice < tempPrices[flightDst]) {
37
            tempPrices[flightDst] = newPrice;
38
            q.offer(flightDst);
39
          }
40
        }
41
      }
42
      for (int i = 0; i < n; i++) // Copy Temp Prices to Original Price Arr
43
      prices[i] = tempPrices[i];
44
      k--;
45
    }
46
    int totalPrice = prices[dst];
47
    return totalPrice == Integer.MAX_VALUE ? -1 : totalPrice;
48
  }
49
}