Minimum Number of Coins for Fruits — Problem & Solution
Minimum Number of Coins for Fruits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Number of Coins for Fruits is a medium coding problem on arrays, dynamic programming and monotonic queue, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Monotonic Queue
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A fruit stall at the CodeKairo meetup lines up n fruits, numbered from 1. Buying the i-th fruit costs prices[i - 1] coins and comes with a reward: the next i fruits (numbers i + 1 to 2i) are yours for free.
You may still pay for a fruit you could take for free — buying it earns its own reward.
Return the minimum number of coins needed to end up with every fruit.
Example 1
Input: prices = [5,2,8]
Output: 7
Explanation: Buy fruit 1 (5 coins) and fruit 2 is free; buy fruit 2 anyway (2 coins) so fruits 3 and 4 are free.
Example 2
Input: prices = [1,10,1,1]
Output: 2
Explanation: Buy fruit 1 (fruit 2 free), then buy fruit 3 (fruit 4 free).
Example 3
Input: prices = [26,18,6,12,49,7,45,45]
Output: 39
Constraints
1 <= prices.length <= 10001 <= prices[i] <= 10^5
Hints for Minimum Number of Coins for Fruits
Hint 1
Fruit 1 can never be free, so it is always bought.
Hint 2
After buying fruit
i, fruits up to2iare covered — the next fruit you must pay for is somewhere ini + 1 .. 2i + 1.Hint 3
Let
dp[i]be the cheapest cost to own fruitsi..ngiven you buy fruiti:prices[i-1] + min(dp[j])forjini + 1 .. 2i + 1, withdp[n + 1] = 0.
How to solve Minimum Number of Coins for Fruits
Think of the purchases in increasing order. After buying fruit i, everything up to 2i is covered, so the next purchase can be any fruit from i + 1 to 2i + 1 — buying earlier than needed is allowed and sometimes cheaper.
Approach
- Create
dpof sizen + 2withdp[n + 1] = 0(nothing left to buy). - For
ifromndown to1:dp[i] = prices[i - 1] + min(dp[j])overjfromi + 1tomin(2i + 1, n + 1). - Return
dp[1], since fruit 1 must be bought.
Why it works
Sort the purchases of any valid plan. Consecutive purchases i < j must satisfy j <= 2i + 1, or fruit 2i + 1 would be neither bought nor covered (earlier purchases cover even less). Conversely, any chain starting at 1 where each step is at most 2i + 1 and the last purchase reaches n covers every fruit. The DP minimises over exactly these chains.
Complexity
- Time —
O(n^2) — a monotonic deque over the window brings it to O(n) - Space —
O(n)
Pitfalls
- Fruits are 1-indexed in the reward rule: fruit
ifreesifruits, so index arithmetic onpricesneedsi - 1. - Greedily taking every free fruit is not optimal — paying for a cheap fruit can unlock a longer free run.
- The window ends at
2i + 1, not2i: that fruit is the first one not covered.
Reference solution
Python
from typing import List
def minimumCoins(prices: List[int]) -> int:
n = len(prices)
dp = [0] * (n + 2)
for i in range(n, 0, -1):
hi = min(2 * i + 1, n + 1)
dp[i] = prices[i - 1] + min(dp[i + 1:hi + 1])
return dp[1]Java
public static int minimumCoins(int[] prices) {
int n = prices.length;
int[] dp = new int[n + 2];
for (int i = n; i >= 1; i--) {
int hi = Math.min(2 * i + 1, n + 1);
int best = Integer.MAX_VALUE;
for (int j = i + 1; j <= hi; j++) best = Math.min(best, dp[j]);
dp[i] = prices[i - 1] + best;
}
return dp[1];
}C++
int minimumCoins(vector<int>& prices) {
int n = prices.size();
vector<int> dp(n + 2, 0);
for (int i = n; i >= 1; i--) {
int hi = min(2 * i + 1, n + 1);
int best = INT_MAX;
for (int j = i + 1; j <= hi; j++) best = min(best, dp[j]);
dp[i] = prices[i - 1] + best;
}
return dp[1];
}JavaScript
var minimumCoins = function(prices) {
var n = prices.length;
var dp = new Array(n + 2).fill(0);
for (var i = n; i >= 1; i--) {
var hi = Math.min(2 * i + 1, n + 1);
var best = Infinity;
for (var j = i + 1; j <= hi; j++) if (dp[j] < best) best = dp[j];
dp[i] = prices[i - 1] + best;
}
return dp[1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming