You are given an 1-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the ith fruit.
The fruit market has the following reward for each fruit:
ith fruit at prices[i] coins, you can get any number of the next i fruits for free.Note that even if you can take fruit j for free, you can still purchase it for prices[j] coins to receive its reward.
Return the minimum number of coins needed to acquire all the fruits.
Example 1:
Input: prices = [3,1,2]
Output: 4
Explanation:
prices[0] = 3 coins, you are allowed to take the 2nd fruit for free.prices[1] = 1 coin, you are allowed to take the 3rd fruit for free.Note that even though you could take the 2nd fruit for free as a reward of buying 1st fruit, you purchase it to receive its reward, which is more optimal.
Example 2:
Input: prices = [1,10,1,1]
Output: 2
Explanation:
prices[0] = 1 coin, you are allowed to take the 2nd fruit for free.prices[2] = 1 coin, you are allowed to take the 4th fruit for free.Example 3:
Input: prices = [26,18,6,12,49,7,45,45]
Output: 39
Explanation:
prices[0] = 26 coin, you are allowed to take the 2nd fruit for free.prices[2] = 6 coin, you are allowed to take the 4th, 5th and 6th (the next three) fruits for free.prices[5] = 7 coin, you are allowed to take the 8th and 9th fruit for free.Note that even though you could take the 6th fruit for free as a reward of buying 3rd fruit, you purchase it to receive its reward, which is more optimal.
Constraints:
1 <= prices.length <= 10001 <= prices[i] <= 105Problem Overview: You are given an array prices where prices[i] represents the cost of buying the i-th fruit. When you buy fruit i, you can take the next i fruits for free. The goal is to buy fruits in a way that covers the entire array while minimizing the total number of coins spent.
Approach 1: Greedy with Priority Queue (O(n log n) time, O(n) space)
This method treats each purchase as a decision point and uses a min-heap to track the cheapest valid way to reach future fruits. While iterating through the array, push possible purchase states into a priority queue storing the total cost and the farthest index the purchase can cover. If the current index exceeds the coverage of the cheapest state, remove it from the heap. The smallest accumulated cost always represents the best way to cover the current fruit. This greedy strategy works because the heap maintains the minimum cost among all active purchase options.
Approach 2: Dynamic Programming with Monotonic Queue (O(n) time, O(n) space)
Define dp[i] as the minimum coins needed starting from fruit i. Buying fruit i costs prices[i] and allows you to skip to any position between i+1 and i+i+1. The recurrence becomes dp[i] = prices[i] + min(dp[j]) for all reachable j. Computing this naively costs O(n²), so maintain a sliding minimum using a monotonic queue. Process indices from right to left and keep the deque increasing by dp values, which lets you query the minimum transition in O(1). This transforms the dynamic programming transition into a linear-time solution.
Both solutions rely heavily on efficient range minimum tracking using structures like a heap (priority queue) or a monotonic queue. The DP formulation also demonstrates a classic optimization pattern in dynamic programming where a sliding window minimum removes nested loops.
Recommended for interviews: The dynamic programming approach with a monotonic queue is the expected optimal solution. It reduces the naive transition from O(n²) to O(n) while keeping the logic clean and deterministic. Starting with the basic DP recurrence shows understanding of the problem structure, and then optimizing it with a deque demonstrates strong algorithmic skills.
The Greedy Approach involves starting from the most expensive fruit and moving downwards. By purchasing the costly fruits which have the potential to give maximum savings by allowing multiple subsequent fruits for free, we minimize the total number of coins required for purchasing all fruits. Prioritize buying fruits that eliminate the need to buy several subsequent fruits.
The function minCoins calculates the minimum coins required to buy all the fruits. It iterates from the end of the prices array towards the start, accumulating the cost and effectively skipping the number of steps based on the index being processed.
Time Complexity: O(n), where n is the number of fruits.
Space Complexity: O(1), as it uses only constant space.
The Dynamic Programming Approach constructs a solution where at each step, it calculates the minimum cost of purchasing all fruits up to that point. It uses a state array dp[i] representing the minimum cost to buy up to the ith fruit. The idea is to leverage previously computed results for efficient calculation.
This DP approach in C uses an array `dp` to keep track of the minimum coins needed for different lengths of the fruits considered. By iterating and updating with the smallest costs, it ultimately provides the optimal result.
Time Complexity: O(n^2), where n is the number of fruits.
Space Complexity: O(n).
We define a function dfs(i) to represent the minimum number of coins needed to buy all the fruits starting from the i-th fruit. The answer is dfs(1).
The execution logic of the function dfs(i) is as follows:
i times 2 geq n, it means that buying the (i - 1)-th fruit is sufficient, and the remaining fruits can be obtained for free, so return prices[i - 1].i, and then choose a fruit j to start buying from the next i + 1 to 2i + 1 fruits. Thus, dfs(i) = prices[i - 1] + min_{i + 1 \le j \le 2i + 1} dfs(j).To avoid redundant calculations, we use memoization to store the results that have already been computed. When encountering the same situation again, we directly return the result.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array prices.
Python
Java
C++
Go
TypeScript
We can rewrite the memoization search in Solution 1 into a dynamic programming form.
Similar to Solution 1, we define f[i] to represent the minimum number of coins needed to buy all the fruits starting from the i-th fruit. The answer is f[1].
The state transition equation is f[i] = min_{i + 1 \le j \le 2i + 1} f[j] + prices[i - 1].
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array prices.
In the code implementation, we can directly use the prices array to store the f array, thus optimizing the space complexity to O(1).
Python
Java
C++
Go
TypeScript
Observing the state transition equation in Solution 2, we can see that for each i, we need to find the minimum value of f[i + 1], f[i + 2], cdots, f[2i + 1]. As i decreases, the range of these values also decreases. This is essentially finding the minimum value in a sliding window with a narrowing range, which can be optimized using a monotonic queue.
We calculate from back to front, maintaining a monotonically increasing queue q, where the queue stores indices. If the front element of q is greater than i times 2 + 1, it means that the elements after i will not be used, so we dequeue the front element. If i is not greater than (n - 1) / 2, we can add prices[q[0] - 1] to prices[i - 1], and then add i to the back of the queue. If the fruit price corresponding to the back element of q is greater than or equal to prices[i - 1], we dequeue the back element until the fruit price corresponding to the back element is less than prices[i - 1] or the queue is empty, then add i to the back of the queue.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array prices.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the number of fruits. |
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the number of fruits. |
| Memoization Search | — |
| Dynamic Programming | — |
| Dynamic Programming + Monotonic Queue Optimization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Priority Queue | O(n log n) | O(n) | Useful when modeling the problem as active purchase ranges and selecting the cheapest valid state using a heap |
| Dynamic Programming + Monotonic Queue | O(n) | O(n) | Best choice for interviews and large inputs where the DP transition needs fast sliding window minimum queries |
2944. Minimum Number of Coins for Fruits • Ayush Rao • 1,862 views views
Watch 8 more video solutions →Practice Minimum Number of Coins for Fruits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor