Cheapest Flights Within K Stops LeetCode

The Cheapest Flights Within K Stops is a coding problem that imposes the challenge of efficiently navigating through a network of cities while minimizing travel costs. This problem not only sharpens one’s skills in graph traversal and dynamic programming, but also encourages the exploration of optimal strategies to find the most economical routes within a specified number of stops. Solving Cheapest Flights Within K Stops LeetCode problem will help you enhance your problem-solving abilities while understanding the algorithm which is crucial for real-world applications in logistics and transportation.

Problem statement

There are n cities connected by a certain number of flights. Each flight is represented by an array flights where flights[i] = [from_city_i, to_city_i, price_i]. This means there’s a flight from city from_city_i to city to_city_i with a ticket price price_i.

Other than n and flights, there are three other input variables:

src: The starting city from where the journey will begin.
dst: The destination city where the journey will end.
k: The maximum number of stops that can be made during the journey.

The task is to find the cheapest price to travel from city src to city dst, with the constraint that there can be at most k stops. If it’s not possible to reach dst from src within k stops, return -1.

Constraints

$1 \leq$ n $\leq 100$
$0 \leq$ flights.length $\leq (n \times (n - 1) / 2)$
flights[i].length $== 3$
$0 \leq$ from_city, to_city $< n$
from_city $\neq$ to_city
$1 \leq$ price_i $\leq 10^4$
There will not be any multiple flights between the two cities.
$0 \leq$ src, dst, k $< n$
src $\neq$ dst

Solution

Now that we’ve comprehended the problem, let’s dive into its programmatic solution. The task at hand is to find the cheapest flight from a source city to a destination city within a specified number of stops. This algorithm efficiently navigates through the flight network to determine the most economical route.

Here’s a breakdown of how the algorithm works:

We initialize an adjacency list to represent the flight connections between cities for efficient graph traversal.
To keep track of the cost to reach each city, we initialize a list output with costs set to infinity initially.
- The cost to reach the source city src is set to 0, as there are no costs associated with reaching the starting point.
We build the adjacency list from the provided flights data, organizing cities and their flight connections.
Using the Breadth-First Search (BFS) traversal technique, we explore the graph starting from the source city src.
We employ a deque (double-ended queue) to manage nodes for exploration during BFS traversal. The deque is initialized with the source city src, indicating the beginning of the traversal.
While there are nodes in the traversal queue:
- We dequeue a node, along with its number of stops and current cost.
- If the number of stops exceeds the specified limit k, we skip exploration from that node to avoid exceeding the maximum number of stops.
- For each neighboring city of the dequeued node:
  - We calculate the cost to reach the neighbor by adding the price element from flights to the current cost.
  - If this new cost is less than the previously stored cost to reach the neighbor, we update the cost.
  - The neighbor with the updated number of stops and cost is enqueued for further exploration.
After completing BFS traversal, we check if the cost to reach the destination city remains infinity.
- If so, it indicates that the destination is unreachable within the specified number of stops, and we return -1.
- Otherwise, we return the minimum cost to reach the destination city dst from the source city src.

By following this systematic approach, we efficiently navigate through the flight network, identifying the cheapest route from the source city src to the destination city dst within the designated number of stops k.

Let’s implement our approach in Python and use the graphs given above as test cases.

from collections import deque
def findCheapestPrice(n, flights, src, dst, k):
    adj_graph = [[]for _ in range(n)]          # Adjacency list for graph representation
    output = [float('inf') for _ in range(n)]  # Costs list initialized with infinity
    output[src] = 0  
    # Building adjacency list from flights data
    for u, v, w in flights:
        adj_graph[u].append((v, w))  
        
    BFS_traversal = deque()                     # Breadth-first search (BFS) traversal queue
    BFS_traversal.append((src, -1, 0))          # Enqueue source node with stops and cost
    while BFS_traversal:
        u, stops, cost = BFS_traversal.popleft()# Dequeue node, stops, and cost
        if stops >= k:
            continue                            # Skip node if number of stops exceeds limit 'k'
        for v, w in adj_graph[u]:
            if cost+w < output[v]:
                output[v] = cost+w              # Update cost if shorter path is found
                BFS_traversal.append((v, stops+1, cost+w))  # Enqueue neighbor with updated stops and cost
    # Return -1 if destination is unreachable; otherwise, return cost
    return -1 if output[dst] == float('inf') else output[dst]  
# Test cases
example1 = [4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1]
example2 = [3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1]
example3 = [3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0]
print("Cheapest flight for example 1: ", findCheapestPrice(example1[0], example1[1], example1[2], example1[3], example1[4])) #700
# print("Cheapest flight for example 2: ", findCheapestPrice(example2[0], example2[1], example2[2], example2[3], example2[4])) #200
# print("Cheapest flight for example 3: ", findCheapestPrice(example3[0], example3[1], example3[2], example3[3], example3[4])) #500

Now that we have a solution for this LeetCode problem, let’s analyze its time and space complexity to understand how efficiently it scales with large inputs.

Time complexity

The time complexity of the provided code is $O(V + E)$ , where $V$ is the number of vertices (n) and $E$ is the number of edges (number of flights). This complexity arises from the BFS traversal, where each vertex and edge is visited at most once. In the worst case, every edge in the adjacency list is traversed, contributing to the linear time complexity. Thus, the overall time complexity is determined by the size of the graph representation.

Space complexity

The space complexity of the provided code is $O(V)$ , where $V$ is the number of vertices (n) in the graph. This is primarily due to the storage of the adjacency list (adj_graph) representing the graph, which consumes space proportional to the number of vertices. Additionally, the BFS traversal queue (BFS_traversal) may contain at most all vertices and their associated data (node, stops, cost), contributing to the linear space complexity. Therefore, the space required is primarily determined by the size of the graph representation and the BFS traversal queue.

Continue learning with Educative

This is only a single coding problem. If you want to explore more coding challenges that can help prepare you for interviews at major tech companies, consider exploring the following blogs by Educative:

Free Resources