LeetCode 2093: Minimum Cost to Reach City With Discounts Solution

Master LeetCode problem 2093 (Minimum Cost to Reach City With Discounts), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2093. Minimum Cost to Reach City With Discounts

Medium

Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm with a slight modification. We will create a graph where each node represents a city and each edge represents a flight between two cities. We will keep track of the cost to reach each city with and without the discount.

Initialize a priority queue to store the cities with their current cost.
Initialize two arrays, cost and discountCost, to store the minimum cost to reach each city without and with a discount, respectively. Initialize all values in both arrays to infinity except for the starting city, which will be 0 in cost and discountCost.
Add the starting city to the priority queue with cost 0.
While the priority queue is not empty:
- Pop the city with the minimum cost from the priority queue.
- For each flight from this city to a neighboring city:
  - Calculate the cost to reach the neighboring city without a discount (newCost) and with a discount (newDiscountCost).
  - If newCost or newDiscountCost is less than the current cost to reach the neighboring city, update the cost and discountCost arrays accordingly.
  - Add the neighboring city to the priority queue with the updated cost or discountCost.
Return the minimum cost to reach the destination city with or without a discount, whichever is smaller.

Solution Code

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] flight : flights) {
            graph.putIfAbsent(flight[0], new ArrayList<>());
            graph.get(flight[0]).add(new int[]{flight[1], flight[2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, src, k + 1});

        int[] cost = new int[n];
        int[] discountCost = new int[n];
        Arrays.fill(cost, Integer.MAX_VALUE);
        Arrays.fill(discountCost, Integer.MAX_VALUE);
        cost[src] = 0;
        discountCost[src] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currCost = curr[0];
            int currCity = curr[1];
            int stops = curr[2];

            if (currCity == dst) {
                return currCost;
            }

            if (stops > 0) {
                List<int[]> neighbors = graph.getOrDefault(currCity, new ArrayList<>());
                for (int[] neighbor : neighbors) {
                    int newCost = currCost + neighbor[1];
                    int newDiscountCost = currCost + neighbor[1] / 2;
                    if (newCost < cost[neighbor[0]]) {
                        cost[neighbor[0]] = newCost;
                        pq.offer(new int[]{newCost, neighbor[0], stops - 1});
                    }
                    if (newDiscountCost < discountCost[neighbor[0]]) {
                        discountCost[neighbor[0]] = newDiscountCost;
                        pq.offer(new int[]{newDiscountCost, neighbor[0], stops - 1});
                    }
                }
            }
        }

        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2093 (Minimum Cost to Reach City With Discounts)?

This page provides optimized solutions for LeetCode problem 2093 (Minimum Cost to Reach City With Discounts) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2093 (Minimum Cost to Reach City With Discounts)?

The time complexity for LeetCode 2093 (Minimum Cost to Reach City With Discounts) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2093 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2093 in Java, C++, or Python.

Back to LeetCode Solutions