Skip to main content
Talentd

Minimum Cost to Buy Apples II - Solution & Explanation

HardArrayGraphHeap (Priority Queue)Shortest Path5 min readAsked at: Amazon
Practice this problem

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:

  • ui and vi are the shops connected by the road.
  • costi is the cost to travel the road without carrying apples.
  • taxi is the multiplier applied to costi when traveling with apples.

For each shop i, you can either:

  • Buy apples locally at shop i for prices[i].
  • Travel empty to any shop j using any number of roads, buy apples for prices[j], and return to shop i while carrying apples, paying cost * tax on 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 <= 1000
  • prices.length == n
  • 1 <= prices[i] <= 109
  • 0 <= roads.length <= min(n × (n - 1) / 2, 2000)
  • roads[i] = [ui, vi, costi, taxi]
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 1 <= 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Floyd–Warshall All-Pairs Shortest PathO(n^3)O(n^2)Small graphs where implementing all-pairs distances is simpler
Dijkstra from Every CityO(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

Video Solution

weekly contest 501| leetcode 3925 | leetcode 3926| leetcode 3927| leetcode 3928| Dijkstra| DSA • Code With Vick • 558 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Cost to Buy Apples II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays