LeetCode 787 - Cheapest Flights Within K Stops

Here’s a complete, detailed technical solution guide for LeetCode 787, following your formatting instructions exactly. The problem asks us to find the cheapest flight cost from a source city src to a destination city dst while taking at most k stops along the way.

leetcodemediumdynamic-programmingdepth-first-searchbreadth-first-searchgraph-theoryheap-(priority-queue)shortest-path

LeetCode Problem 787

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Here’s a complete, detailed technical solution guide for LeetCode 787, following your formatting instructions exactly.

Problem Understanding

The problem asks us to find the cheapest flight cost from a source city src to a destination city dst while taking at most k stops along the way. We are given n cities and a list of flights where each flight is represented as [from, to, price]. The input is effectively a weighted directed graph, where nodes are cities and edges are flights with associated costs. The goal is to find the minimum total edge weight path from src to dst that uses at most k + 1 edges (since k stops means k + 1 flights).

The constraints provide useful hints about input scale. n is up to 100, and the number of flights is at most n * (n - 1) / 2 (complete graph without duplicates). Prices are positive integers, so we do not have to handle negative cycles. k is always less than n, so the path length is bounded. The problem guarantees no multiple edges between the same pair of cities, and src != dst.

Important edge cases include k = 0 (direct flights only), disconnected graphs where no path exists, and situations where multiple paths exist but only paths with at most k stops are allowed.

Approaches

Brute Force

A naive approach is to perform a DFS from src, exploring all paths to dst with at most k stops. Each recursive call tracks the remaining stops and accumulated cost. This approach is correct because it examines all valid paths, but it is too slow. In the worst case, the recursion explores every possible path of length up to k + 1, leading to exponential time complexity, which is unacceptable for n = 100.

Optimal Approach

The key insight is to notice that the maximum number of flights allowed is k + 1. This makes the Bellman-Ford dynamic programming algorithm an ideal fit. Bellman-Ford allows us to compute shortest paths with a bounded number of edges by repeatedly relaxing edges. Each iteration relaxes all edges once, effectively considering paths with one more edge. By performing k + 1 iterations, we ensure all paths with at most k stops are considered. This avoids exploring unnecessary paths and runs efficiently with the given constraints.

Another alternative is a modified Dijkstra's algorithm with a priority queue, tracking both cost and remaining stops. This works but can be more complex to implement correctly because we must carefully track the stop limit to avoid revisiting nodes unnecessarily.

Approach Time Complexity Space Complexity Notes
Brute Force DFS O(n^(k+1)) O(n) Explores all paths recursively, exponential and infeasible
Bellman-Ford DP O((k+1) * flights) O(n) Iterative edge relaxation bounded by stops, efficient and simple
Dijkstra with stops O(flights * log(n)) O(n) Uses priority queue, handles stop constraint carefully

Algorithm Walkthrough

  1. Initialize a list dist of size n to track the minimum cost to reach each city. Set dist[src] = 0 and all others to infinity.

  2. Perform k + 1 iterations (each iteration corresponds to allowing one more flight). In each iteration:

  3. Copy the current dist to temp to avoid in-place updates that could use newly relaxed edges prematurely.

  4. For every flight [from, to, price], check if taking this flight from from improves the cost to reach to. If dist[from] + price < temp[to], update temp[to].

  5. After all flights are relaxed for this iteration, update dist with temp.

  6. After k + 1 iterations, dist[dst] holds the minimum cost to reach dst with at most k stops. If it remains infinity, return -1.

Why it works: Bellman-Ford guarantees that after i iterations, dist[j] contains the minimum cost to reach node j using at most i edges. By performing k + 1 iterations, we account for all paths with at most k stops.

Python Solution

from typing import List

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        INF = float('inf')
        dist = [INF] * n
        dist[src] = 0

        for i in range(k + 1):
            temp = dist.copy()
            for from_city, to_city, price in flights:
                if dist[from_city] != INF and dist[from_city] + price < temp[to_city]:
                    temp[to_city] = dist[from_city] + price
            dist = temp

        return -1 if dist[dst] == INF else dist[dst]

This code initializes distances, iterates k + 1 times, relaxes all edges carefully using a copy to avoid overwriting distances prematurely, and returns the final minimum cost or -1 if unreachable.

Go Solution

import "math"

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    INF := math.MaxInt32
    dist := make([]int, n)
    for i := 0; i < n; i++ {
        dist[i] = INF
    }
    dist[src] = 0

    for i := 0; i <= k; i++ {
        temp := make([]int, n)
        copy(temp, dist)
        for _, flight := range flights {
            from, to, price := flight[0], flight[1], flight[2]
            if dist[from] != INF && dist[from]+price < temp[to] {
                temp[to] = dist[from] + price
            }
        }
        dist = temp
    }

    if dist[dst] == INF {
        return -1
    }
    return dist[dst]
}

The Go implementation mirrors the Python logic, using math.MaxInt32 for infinity and copy to avoid premature updates.

Worked Examples

Example 1: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Iteration dist array Explanation
0 [0, inf, inf, inf] initial
1 [0, 100, inf, 700] relax edges once, direct flight 0->1, 1->3 via 0->1
2 [0, 100, 200, 700] relax edges again, path 0->1->2 considered, but stop limit prevents 0->1->2->3

Result: 700

Example 2: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Iteration dist array
0 [0, inf, inf]
1 [0, 100, 500]
2 [0, 100, 200]

Result: 200

Example 3: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Only direct flights allowed.

Result: 500

Complexity Analysis

Measure Complexity Explanation
Time O((k+1) * flights) We perform k+1 iterations, relaxing all flights each time
Space O(n) We store distance array and temporary copy

The time complexity is efficient because flights is at most n*(n-1)/2, giving a practical upper bound of roughly 5000 for n=100.

Test Cases

sol = Solution()

# Provided examples
assert sol.findCheapestPrice(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1) == 700
assert sol.findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) == 200
assert sol.findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0) == 500

# Edge cases
assert sol.findCheapestPrice(2, [], 0, 1, 0) == -1 # no flights
assert sol.findCheapestPrice(3, [[0,1,100]], 0, 2, 1) == -1 # dst unreachable
assert sol.find