Skip to main content
Talentd

Minimum Cost to Buy Apples - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGraphHeap (Priority Queue)Shortest Path8 min readAsked at: Directi, Medianet
Practice this problem

Problem Statement

You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads, where roads[i] = [ai, bi, costi] indicates that there is a bidirectional road between cities ai and bi with a cost of traveling equal to costi.

You can buy apples in any city you want, but some cities have different costs to buy apples. You are given the 1-based array appleCost where appleCost[i] is the cost of buying one apple from city i.

You start at some city, traverse through various roads, and eventually buy exactly one apple from any city. After you buy that apple, you have to return back to the city you started at, but now the cost of all the roads will be multiplied by a given factor k.

Given the integer k, return a 1-based array answer of size n where answer[i] is the minimum total cost to buy an apple if you start at city i.

 

Example 1:

Input: n = 4, roads = [[1,2,4],[2,3,2],[2,4,5],[3,4,1],[1,3,4]], appleCost = [56,42,102,301], k = 2
Output: [54,42,48,51]
Explanation: The minimum cost for each starting city is the following:
- Starting at city 1: You take the path 1 -> 2, buy an apple at city 2, and finally take the path 2 -> 1. The total cost is 4 + 42 + 4 * 2 = 54.
- Starting at city 2: You directly buy an apple at city 2. The total cost is 42.
- Starting at city 3: You take the path 3 -> 2, buy an apple at city 2, and finally take the path 2 -> 3. The total cost is 2 + 42 + 2 * 2 = 48.
- Starting at city 4: You take the path 4 -> 3 -> 2 then you buy at city 2, and finally take the path 2 -> 3 -> 4. The total cost is 1 + 2 + 42 + 1 * 2 + 2 * 2 = 51.

Example 2:

Input: n = 3, roads = [[1,2,5],[2,3,1],[3,1,2]], appleCost = [2,3,1], k = 3
Output: [2,3,1]
Explanation: It is always optimal to buy the apple in the starting city.

 

Constraints:

  • 2 <= n <= 1000
  • 1 <= roads.length <= 2000
  • 1 <= ai, bi <= n
  • ai != bi
  • 1 <= costi <= 105
  • appleCost.length == n
  • 1 <= appleCost[i] <= 105
  • 1 <= k <= 100
  • There are no repeated edges.

Approach Overview

Problem Overview: You have n cities connected by weighted roads. Each city sells apples at a specific price. Starting from city i, you can travel to any city j to buy apples and return back. The return trip multiplies road cost by k. For every city, compute the minimum total cost of buying apples and coming back.

Approach 1: Run Dijkstra from Every City (Brute Force Graph Shortest Path) (Time: O(n * (m log n)), Space: O(n))

Treat each city as a starting point. Run Dijkstra to compute the shortest distance from city i to every other city. For each destination j, calculate the purchase cost appleCost[j] + dist(i, j) * (k + 1). Track the minimum value. This works because traveling to j and returning multiplies each road cost by (k + 1). The downside is obvious: running a full shortest-path search for every city is expensive when n is large.

Approach 2: Multi‑Source Dijkstra with Heap Optimization (Time: O((n + m) log n), Space: O(n))

The key insight: the cost formula appleCost[j] + (k + 1) * dist(i, j) can be interpreted as a shortest-path problem starting from all apple cities simultaneously. Initialize a priority queue with every city j using distance appleCost[j]. When relaxing edges, scale each road weight by (k + 1). Running a single shortest path search propagates the cheapest apple purchase cost to every city. The heap (priority queue) always expands the currently cheapest state, just like standard graph Dijkstra.

This transforms the problem into a classic multi‑source shortest path. Instead of asking "where should city i go to buy apples", the algorithm spreads the apple prices outward across the graph with adjusted edge weights.

Recommended for interviews: The heap‑optimized multi‑source Dijkstra approach. Interviewers expect you to recognize the shortest‑path structure and reduce repeated computations. Explaining the brute‑force per‑city Dijkstra first shows baseline reasoning, while the multi‑source optimization demonstrates strong graph intuition.

Solution

We enumerate the starting point, and for each starting point, we use Dijkstra's algorithm to find the shortest distance to all other points, and update the minimum value accordingly.

The time complexity is O(n times m times log m), where n and m are the number of cities and roads, respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Run Dijkstra from Every CityO(n * (m log n))O(n)Small graphs where repeated shortest-path runs are acceptable
Multi-Source Heap-Optimized DijkstraO((n + m) log n)O(n)General case and optimal solution for large graphs

Video Solution

2473. Minimum Cost to Buy Apples (Leetcode Medium) • Programming Live with Larry • 632 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Minimum Cost to Buy Apples easy or hard?
Minimum Cost to Buy Apples is rated Medium difficulty on LeetCode. The challenge is recognizing that the cost formula can be modeled as a shortest-path problem and optimized using multi-source Dijkstra instead of running Dijkstra from every city.
Minimum Cost to Buy Apples Python/Java solution
Implement multi-source Dijkstra using a priority queue. Start with all cities in the heap with their apple cost, then relax edges with weight multiplied by (k + 1). The same algorithm works across Python, Java, C++, and Go using their standard priority queue libraries.
What is the best approach for Minimum Cost to Buy Apples?
The optimal approach uses multi-source Dijkstra's algorithm. Initialize a min-heap with every city using its apple price as the starting cost, then relax edges with weight multiplied by (k + 1). This computes the minimum value of appleCost[j] + dist(i, j) * (k + 1) for every city in O((n + m) log n) time.
How to solve Minimum Cost to Buy Apples in O((n+m) log n)?
Run a multi-source Dijkstra. Push all cities into the priority queue with their apple prices as initial distances. When traversing an edge with weight w, treat its cost as w * (k + 1). The resulting shortest distance for each city represents the cheapest possible apple purchase and return cost.
Is Minimum Cost to Buy Apples asked at Google/Amazon/Meta?
Graph shortest-path problems similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving Dijkstra, weighted graphs, and priority queues are common system design and algorithm screening questions.
What data structure is used in Minimum Cost to Buy Apples?
The core data structure is a min-heap (priority queue) used by Dijkstra's algorithm. The graph is typically stored using an adjacency list, allowing efficient edge traversal and heap-based distance updates.
What is the time complexity of Minimum Cost to Buy Apples?
The optimal heap-optimized Dijkstra solution runs in O((n + m) log n) time, where n is the number of cities and m is the number of roads. Each edge relaxation uses a priority queue operation, which dominates the complexity.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays