Minimum Cost to Reach City With Discounts

Medium

Asked by:

1 view

Topics:

GraphsDynamic Programming

A directed weighted graph with n nodes numbered from 0 to n - 1 is given. The graph is represented by an array edges where edges[i] = [u_i, v_i, w_i] means that there is a directed edge from node u_i to node v_i with weight w_i.

You are also given an integer maxMoves, and an integer maxCost.

You start at node 0, and want to reach node n - 1 by using at most maxMoves moves and such that the cost of your path is less than or equal to maxCost.

You are allowed to use at most one discount. If you use a discount on the edge i, the cost of the edge will be w_i / 2 (integer division).

Return the minimum cost to reach the node n - 1 given that you can use at most maxMoves moves and can use at most one discount. If it is not possible to reach the node n - 1 return -1.

Example 1:

Input: n = 5, edges = [[0,1,4],[1,2,3],[1,3,5],[0,3,8],[2,3,1],[3,4,2],[2,4,6]], maxMoves = 5, maxCost = 24
Output: 10
Explanation: One possible way to reach node 4 from node 0 is to use the path 0 -> 1 -> 2 -> 3 -> 4.
The cost for this path is 4 + 3 + 1 + 2 = 10, which does not exceed maxCost = 24. Also, the length of this path is 4, which does not exceed maxMoves = 5.
To get a better answer, we can use a discount on edge 0 -> 1. Now the cost of the path becomes 2 + 3 + 1 + 2 = 8, which is less than 10. So the answer is 8.

Example 2:

Input: n = 4, edges = [[0,1,3],[0,2,2],[1,3,4],[2,3,5]], maxMoves = 4, maxCost = 10
Output: -1
Explanation: It is impossible to reach node 3 from node 0 using at most 4 moves and such that the cost of your path is less than or equal to 10.

Example 3:

Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,9]], maxMoves = 1, maxCost = 10
Output: -1
Explanation: It is impossible to reach node 2 from node 0 using at most 1 move because the edges 0 -> 1 -> 2 will take at least 2 moves.

Constraints:

2 <= n <= 100
0 <= edges.length <= 300
edges[i].length == 3
0 <= u_i, v_i <= n - 1
1 <= w_i <= 1000
1 <= maxMoves <= 100
1 <= maxCost <= 1000

Try coding it in LeetCode

Minimum Cost to Reach City With Discounts

Medium

Asked by:

1 view

Topics:

GraphsDynamic Programming

A directed weighted graph with n nodes numbered from 0 to n - 1 is given. The graph is represented by an array edges where edges[i] = [u_i, v_i, w_i] means that there is a directed edge from node u_i to node v_i with weight w_i.

You are also given an integer maxMoves, and an integer maxCost.

You start at node 0, and want to reach node n - 1 by using at most maxMoves moves and such that the cost of your path is less than or equal to maxCost.

You are allowed to use at most one discount. If you use a discount on the edge i, the cost of the edge will be w_i / 2 (integer division).

Return the minimum cost to reach the node n - 1 given that you can use at most maxMoves moves and can use at most one discount. If it is not possible to reach the node n - 1 return -1.

Example 1:

Input: n = 5, edges = [[0,1,4],[1,2,3],[1,3,5],[0,3,8],[2,3,1],[3,4,2],[2,4,6]], maxMoves = 5, maxCost = 24
Output: 10
Explanation: One possible way to reach node 4 from node 0 is to use the path 0 -> 1 -> 2 -> 3 -> 4.
The cost for this path is 4 + 3 + 1 + 2 = 10, which does not exceed maxCost = 24. Also, the length of this path is 4, which does not exceed maxMoves = 5.
To get a better answer, we can use a discount on edge 0 -> 1. Now the cost of the path becomes 2 + 3 + 1 + 2 = 8, which is less than 10. So the answer is 8.

Example 2:

Input: n = 4, edges = [[0,1,3],[0,2,2],[1,3,4],[2,3,5]], maxMoves = 4, maxCost = 10
Output: -1
Explanation: It is impossible to reach node 3 from node 0 using at most 4 moves and such that the cost of your path is less than or equal to 10.

Example 3:

Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,9]], maxMoves = 1, maxCost = 10
Output: -1
Explanation: It is impossible to reach node 2 from node 0 using at most 1 move because the edges 0 -> 1 -> 2 will take at least 2 moves.

Constraints:

2 <= n <= 100
0 <= edges.length <= 300
edges[i].length == 3
0 <= u_i, v_i <= n - 1
1 <= w_i <= 1000
1 <= maxMoves <= 100
1 <= maxCost <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum values for 'n', 'costi', and 'discounts'?
Is it guaranteed that there is a path from city 0 to city n-1? If not, what should I return if no path exists?
Can there be multiple roads between the same two cities? If so, should I consider the cheapest one?
Are the city indices 0 to n-1, or can they be arbitrary integers?
Can 'costi' be a floating-point number, or is it always an integer? If floating point, what precision should I consider?

Brute Force Solution

Approach

The brute force method for this problem is like exploring every single route to the destination city. We try every possible combination of roads, with and without using the discount, and figure out the total cost for each route.

Here's how the algorithm would work step-by-step:

Start at the beginning city.
Consider every possible road you can take from your current city to the next one.
For each of those roads, calculate the cost of traveling on it. If you haven't used your discount yet, you can choose to use it on that road.
Keep track of the total cost to get to each new city via that particular route.
Repeat these steps for each city you reach, until you arrive at the destination city.
You will likely find many different routes to the destination.
Compare the total cost of all those routes to find the one with the lowest cost. That's the answer!

Code Implementation

def min_cost_brute_force(number_of_cities, roads, discount):
    min_total_cost = float('inf')

    def explore_routes(current_city, current_cost, discount_used):
        nonlocal min_total_cost

        # If we've reached the destination, update the minimum cost
        if current_city == number_of_cities - 1:
            min_total_cost = min(min_total_cost, current_cost)
            return

        # Iterate through all available roads from the current city
        for start_city, end_city, road_cost in roads:
            if start_city == current_city:
                # Take the road without using discount
                explore_routes(
                    end_city,
                    current_cost + road_cost,
                    discount_used
                )

                # Consider using the discount if available
                if not discount_used:
                    # Explore with discount
                    explore_routes(
                        end_city,
                        current_cost + road_cost / 2,
                        True
                    )

    explore_routes(0, 0, False)

    return int(min_total_cost)

Big(O) Analysis

Time Complexity

O(3^n) – The brute force approach explores all possible paths in the graph. In the worst-case scenario, where the graph is dense, each node can have multiple outgoing edges. For each edge, we have two choices: either use the discount or not, and we also have a choice of which path to explore from the current node. This leads to exponential branching, with a factor related to the number of choices at each node. In a graph with n nodes, the number of possible paths can grow exponentially, specifically on the order of 3^n due to path selection and discount option. Therefore, the time complexity is O(3^n).

Space Complexity

O(2^N) – The brute force method explores every possible route, which involves considering all combinations of roads with and without discounts. In the worst-case scenario, where each city has multiple outgoing roads, the number of possible routes can grow exponentially. This requires storing information about each route, such as the cities visited and the cost to reach each city, resulting in a tree-like structure of explored paths. Therefore, the space complexity is O(2^N), where N represents the number of cities, as the number of routes to explore can double with each city encountered.

Optimal Solution

Approach

To find the minimum cost to reach a city with discounts, we use a smart pathfinding technique. We explore possible routes, keeping track of the cheapest cost to reach each city at each possible discount level, and then find the lowest cost to the final city.

Here's how the algorithm would work step-by-step:

Imagine you're exploring a map of cities and roads, and you want to find the cheapest way to reach your destination.
As you travel, you have a limited number of discount coupons you can use to reduce the cost of certain roads.
Keep track of the cheapest way to reach each city with each possible number of discount coupons you still have.
Start from the first city with the full set of discount coupons. Calculate the cost to travel to the neighboring cities using a regular ticket or a discount, if you still have discounts left.
Update the minimum cost to reach each neighboring city, remembering how many discount coupons were used to get there.
Repeat this process by always exploring from the city you can reach the cheapest so far, considering all available options (using a coupon or not).
Continue this until you have explored all possible routes, or until you find a route to the destination that you know is cheaper than any other possible path.
The cheapest cost to reach the destination city, considering all possible discount scenarios, is your answer.

Code Implementation

import heapq

def minimum_cost_to_reach_city_with_discounts(number_of_cities, flights, starting_city, destination_city, number_of_discounts):
    adjacency_list = [[] for _ in range(number_of_cities)]
    for source, destination, cost in flights:
        adjacency_list[source].append((destination, cost))

    # cost[city][discounts_remaining] = min_cost
    cost = [[float('inf')] * (number_of_discounts + 1) for _ in range(number_of_cities)]
    cost[starting_city][number_of_discounts] = 0

    priority_queue = [(0, starting_city, number_of_discounts)]

    while priority_queue:
        current_cost, current_city, discounts_remaining = heapq.heappop(priority_queue)

        if current_cost > cost[current_city][discounts_remaining]:
            continue

        # Explore neighbors
        for neighbor, flight_cost in adjacency_list[current_city]:
            # Option 1: Don't use a discount
            new_cost_no_discount = current_cost + flight_cost

            if new_cost_no_discount < cost[neighbor][discounts_remaining]:
                cost[neighbor][discounts_remaining] = new_cost_no_discount
                heapq.heappush(priority_queue, (new_cost_no_discount, neighbor, discounts_remaining))

            # Option 2: Use a discount, if available
            if discounts_remaining > 0:

                new_cost_with_discount = current_cost + (flight_cost / 2)

                # Check if this path is better than previous ones
                if new_cost_with_discount < cost[neighbor][discounts_remaining - 1]:

                    # Update the cost
                    cost[neighbor][discounts_remaining - 1] = new_cost_with_discount

                    # Add to the priority queue for further exploration
                    heapq.heappush(priority_queue, (new_cost_with_discount, neighbor, discounts_remaining - 1))

    minimum_final_cost = float('inf')

    # Find the minimum cost to reach the destination
    for remaining_discounts in range(number_of_discounts + 1):
        minimum_final_cost = min(minimum_final_cost, cost[destination_city][remaining_discounts])

    if minimum_final_cost == float('inf'):
        return -1

    return int(minimum_final_cost)

Big(O) Analysis

Time Complexity

O(E * D * log(V)) – The algorithm uses a priority queue to explore the graph, where V is the number of vertices (cities), E is the number of edges (roads), and D is the maximum number of discounts allowed. We potentially visit each edge for each possible discount level, leading to E * D iterations. Each iteration involves a priority queue operation (insert or update), which takes O(log(V)) time. Therefore, the overall time complexity is O(E * D * log(V)).

Space Complexity

O(N * discounts) – The algorithm keeps track of the cheapest way to reach each city with each possible number of discount coupons. This is done using a data structure (e.g., a table or array) where each entry stores the minimum cost to reach a city with a specific number of remaining discounts. The size of this data structure is proportional to the number of cities (let's say N) multiplied by the number of possible discounts (discounts). Therefore, the space complexity is O(N * discounts).

Edge Cases

Case	How to Handle
n = 1 (single city)	If starting and ending city are the same, return 0 as no travel is needed.
roads is null or empty	If no roads exist and n > 1, return -1 indicating no path is possible.
discounts = 0 (no discounts allowed)	Run Dijkstra's algorithm without considering discounts for the shortest path.
discounts >= number of roads in the shortest path	Effectively, all roads on the shortest path can be discounted.
No path exists from 0 to n-1	Dijkstra's algorithm will not find a path; return -1.
Graph contains cycles	Dijkstra's algorithm correctly handles cycles by tracking visited nodes and shortest distances.
Large number of cities and roads leading to potential integer overflow in cost calculation	Use long data type to store costs to prevent potential integer overflow.
Invalid city numbers in roads (city < 0 or city >= n)	Check road inputs to validate city number range and throw error if invalid.