Minimum Cost to Buy Apples II solution and explanation
3 more videos on this problem
weekly contest 501| leetcode 3925 | leetcode 3926| leetcode 3927| leetcode 3928| Dijkstra| DSACode With Vick · 40:51 · 558 views
Leetcode 3928 | Minimum Cost to Buy Apples II | Leetcode weekly contest 501 | GraphsCodeWithMeGuys · 22:53 · 461 views
LeetCode 3928 | Minimum Cost to Buy Apples II | Dijkstra | Java | HindiCode Kage · 20:48 · 335 views
3928. Minimum Cost to Buy Apples II (Leetcode Hard)Programming Live with Larry · 25:33 · 155 views
The problem
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 <= 1091 <= taxi <= 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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity 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 |
Frequently asked questions
Is Minimum Cost to Buy Apples II easy or hard?
Minimum Cost to Buy Apples II is considered a Hard problem. The difficulty comes from modeling the purchase and travel costs correctly and recognizing that a multi-source shortest path strategy reduces the complexity to O(m log n).
Minimum Cost to Buy Apples II Python/Java solution
Both Python and Java implementations typically use Dijkstra's algorithm with a priority queue. Python uses heapq for the min-heap, while Java uses PriorityQueue. The adjacency list stores roads and weights, and the algorithm maintains the minimum cost for each city.
How to solve Minimum Cost to Buy Apples II in O(m log n)?
Initialize a priority queue with all cities, using the apple price as the starting distance. Perform a Dijkstra traversal over the road network and relax edges by adding travel cost. Each city keeps the minimum cost discovered so far, producing the final minimum apple purchase cost.
What is the best approach for Minimum Cost to Buy Apples II?
The most efficient approach uses a multi-source Dijkstra algorithm. Treat each apple-selling city as a starting node with its apple price as the initial cost, then propagate travel costs through the graph. This computes the minimum purchase cost for every city in O(m log n) time.
Is Minimum Cost to Buy Apples II asked at Google/Amazon/Meta?
Graph shortest-path optimization problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants involving Dijkstra, multi-source traversal, and cost minimization on weighted graphs are common.
What data structure is used in Minimum Cost to Buy Apples II?
The key data structures are an adjacency list to represent the road network and a min-heap (priority queue) used by Dijkstra's algorithm. These allow efficient edge relaxation and retrieval of the current minimum-cost node.
What is the time complexity of Minimum Cost to Buy Apples II?
The optimal solution runs in O(m log n) time using a priority queue based Dijkstra traversal on the road graph. Space complexity is O(n + m) for storing the adjacency list and distance array.