Minimum Cost to Buy Apples II - Video Solutions
weekly contest 501| leetcode 3925 | leetcode 3926| leetcode 3927| leetcode 3928| Dijkstra| DSA
Minimum Cost to Buy Apples II - Video Solution
Watch 4 video solutions for Minimum Cost to Buy Apples II, a hard level problem involving Array, Graph, Heap (Priority Queue). This walkthrough by Code With Vick has 558 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer n and an integer array prices of length n, where prices[i] is the price of apples at shop i.
You are also given a 2D integer array roads, where roads[i] = [ui, vi, costi, taxi] represents a bidirectional road:
uiandviare the shops connected by the road.costiis the cost to travel the road without carrying apples.taxiis the multiplier applied tocostiwhen traveling with apples.
For each shop i, you can either:
- Buy apples locally at shop
iforprices[i]. - Travel empty to any shop
jusing any number of roads, buy apples forprices[j], and return to shopiwhile carrying apples, payingcost * taxon each road used for the return trip.
The forward path, where you travel empty, and the return path may be different.
Return an integer array ans of length n, where ans[i] is the minimum total cost to buy apples starting from shop i.
Example 1:
Input: n = 2, prices = [8,3], roads = [[0,1,1,2]]
Output: [6,3]
Explanation:
Shop i |
prices[i] |
Shop j |
prices[j] |
costi |
taxi |
Travel cost | Return cost | Total | Minimum |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 8 | 1 | 3 | 1 | 2 | 1 | 1 * 2 = 2 |
1 + 2 + 3 = 6 |
min(8, 6) = 6 |
| 1 | 3 | 0 | 8 | 1 | 2 | 1 | 1 * 2 = 2 |
1 + 2 + 8 = 11 |
min(3, 11) = 3 |
Thus, the answer is [6, 3].
Example 2:
Input: n = 3, prices = [9,4,6], roads = [[0,1,1,3],[1,2,4,2]]
Output: [8,4,6]
Explanation:
​​​​​​​
Shop i |
prices[i] |
Shop j |
prices[j] |
costi |
taxi |
Travel cost | Return cost | Total | Minimum |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 9 | 1 | 4 | 1 | 3 | 1 | 1 * 3 = 3 |
1 + 3 + 4 = 8 |
min(9, 8) = 8 |
| 1 | 4 | 2 | 6 | 4 | 2 | 4 | 4 * 2 = 8 |
4 + 8 + 6 = 18 |
min(4, 18) = 4 |
| 2 | 6 | 1 | 4 | 4 | 2 | 4 | 4 * 2 = 8 |
4 + 8 + 4 = 16 |
min(6, 16) = 6 |
Thus, the answer is [8, 4, 6].
Example 3:
Input: n = 3, prices = [10,11,1], roads = [[0,2,1,3],[1,2,3,4],[0,1,5,2]]
Output: [5,11,1]
Explanation:
​​​​​​​​​​​​​​
Shop i |
prices[i] |
Shop j |
prices[j] |
costi |
taxi |
Travel cost | Return cost | Total | Minimum |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 10 | 2 | 1 | 1 | 3 | 1 | 1 * 3 = 3 |
1 + 3 + 1 = 5 |
min(10, 5) = 5 |
| 1 | 11 | 2 | 1 | 3 | 4 | 3 | 3 * 4 = 12 |
3 + 12 + 1 = 16 |
min(11, 16) = 11 |
| 2 | 1 | 0 | 10 | 1 | 3 | 1 | 1 * 3 = 3 |
1 + 3 + 10 = 14 |
min(1, 14) = 1 |
Thus, the answer is [5, 11, 1].
Constraints:
1 <= n <= 1000prices.length == n1 <= prices[i] <= 1090 <= roads.length <= min(n × (n - 1) / 2, 2000)roads[i] = [ui, vi, costi, taxi]0 <= ui, vi <= n - 1ui != vi1 <= costi <= 109​​​​​​​1 <= tax​​​​​​​i <= 100​​​​​​​- There are no repeated edges.
Approach Overview
Problem Overview: You are given multiple cities connected by roads with travel costs. Each city sells apples at a different price. Starting from any city, you may travel to another city to buy apples and then return. The goal is to compute the minimum total cost (travel + apple price) for each starting city.
Approach 1: Brute Force with All-Pairs Shortest Paths (Floyd–Warshall) (Time: O(n^3), Space: O(n^2))
Compute the shortest distance between every pair of cities using the Floyd–Warshall algorithm. Once all distances are known, iterate through every pair (start, buyCity) and compute the total cost: travel to the city, buy the apple, and return. This approach is straightforward but expensive. With large graphs, the O(n^3) preprocessing dominates runtime and quickly becomes impractical.
Approach 2: Run Dijkstra from Every City (Time: O(n * (m log n)), Space: O(n + m))
Instead of computing all-pairs distances, run graph shortest path from each starting city using Dijkstra's algorithm. The shortest distance to every other city is computed in O(m log n). For each reachable city, calculate the total purchase cost: dist[start][j] + appleCost[j] + returnCost. Repeating this for all starting cities yields the correct answer while avoiding the cubic complexity of Floyd–Warshall.
Approach 3: Optimized Multi-Source Dijkstra (Time: O(m log n), Space: O(n + m))
The optimal solution flips the perspective. Instead of evaluating every start city separately, treat each apple city as a potential source with an initial cost equal to its apple price. Run a multi-source shortest path computation. During relaxation, propagate travel costs through the graph so each node discovers the cheapest place to buy apples. This works because Dijkstra naturally expands the minimum-cost frontier, combining purchase price and travel cost in a single pass.
Recommended for interviews: Start by explaining the brute-force idea with all-pairs distances to demonstrate the correct cost formula. Then move to the Dijkstra-based solution. Interviewers usually expect the optimized shortest-path approach since it reduces the complexity to roughly O(m log n), which scales well for large road networks.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Floyd–Warshall All-Pairs Shortest Path | O(n^3) | O(n^2) | Small graphs where implementing all-pairs distances is simpler |
| Dijkstra from Every City | O(n * (m log n)) | O(n + m) | Moderate graph sizes where repeated shortest-path runs are acceptable |
| Multi-Source Dijkstra (Optimal) | O(m log n) | O(n + m) | Large graphs where you need the most efficient single-pass shortest path solution |