Cheapest Flights Within K Stops: the idea to remember.

The core insight

Relax flights k plus one times using a separate copy of distances for each layer.

Why it works

Each layer adds at most one flight, so after k plus one layers only routes within the flight budget are considered.

The mistake to avoid

Reading newly updated distances in the same layer can incorrectly use extra flights. Stops and flights differ by one.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Relax flights k plus one times using a separate copy of distances for each layer.
public int findCheapestPrice(
    int n,
    int[][] flights,
    int src,
    int dst,
    int k
) {

    int[] prices = new int[n];
    Arrays.fill(prices, Integer.MAX_VALUE);


    prices[src] = 0;

    for (int i = 0; i <= k; i++) {

        int[] temp = new int[n];
        temp = Arrays.copyOf(prices, prices.length);


        for (int j = 0; j < flights.length; j++) {
            int s = flights[j][0]; 
            int d = flights[j][1]; 
            int p = flights[j][2]; 

            if (prices[s] == Integer.MAX_VALUE) {
                continue;
            }

            if (prices[s] + p < temp[d]) {
                temp[d] = prices[s] + p;
            }
        }


        prices = temp;
    }

    if (prices[dst] != Integer.MAX_VALUE) {
        return prices[dst];
    }

    return -1;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection