You are at a fruit market with different types of exotic fruits on display.
You are given a 1-indexed array prices, where prices[i] denotes the number of coins needed to purchase the ith fruit.
The fruit market has the following offer:
ith fruit at prices[i] coins, you can get 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 a new offer.
Return the minimum number of coins needed to acquire all the fruits.
Example 1:
Input: prices = [3,1,2] Output: 4 Explanation: You can acquire the fruits as follows: - Purchase the 1st fruit with 3 coins, and you are allowed to take the 2nd fruit for free. - Purchase the 2nd fruit with 1 coin, and you are allowed to take the 3rd fruit for free. - Take the 3rd fruit for free. Note that even though you were allowed to take the 2nd fruit for free, you purchased it because it is more optimal. It can be proven that 4 is the minimum number of coins needed to acquire all the fruits.
Example 2:
Input: prices = [1,10,1,1] Output: 2 Explanation: You can acquire the fruits as follows: - Purchase the 1st fruit with 1 coin, and you are allowed to take the 2nd fruit for free. - Take the 2nd fruit for free. - Purchase the 3rd fruit for 1 coin, and you are allowed to take the 4th fruit for free. - Take the 4th fruit for free. It can be proven that 2 is the minimum number of coins needed to acquire all the fruits.
Constraints:
1 <= prices.length <= 1051 <= prices[i] <= 105Problem Overview: You are given an array where price[i] is 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 purchase fruits in a way that covers the entire array while minimizing the total number of coins spent.
Approach 1: Brute Force Dynamic Programming (O(n²) time, O(n) space)
Define dp[i] as the minimum cost required to obtain all fruits starting from index i. If you buy fruit i, you pay price[i] and can skip up to i fruits for free. The next paid purchase must happen in the range [i+1, i+i+1]. For every valid next position, compute price[i] + dp[next] and take the minimum. This approach directly follows the problem definition but scans a range of states for every index, leading to quadratic time.
Approach 2: DP with Min Heap (O(n log n) time, O(n) space)
The transition requires the minimum dp[j] in a sliding range of indices. Instead of scanning the range every time, maintain candidate states in a min heap. As you iterate from right to left, push valid dp values and remove entries that fall outside the allowed window [i+1, i+i+1]. The heap always exposes the smallest future cost in O(log n). This significantly improves performance for large inputs while keeping the implementation straightforward using a heap (priority queue).
Approach 3: Monotonic Queue Optimized DP (O(n) time, O(n) space)
The optimal solution observes that the heap is only used to track the minimum dp value in a sliding window. A monotonic queue maintains candidate indices with increasing dp values, allowing constant-time retrieval of the minimum. While iterating backward through the array, remove indices that fall outside the valid purchase window and maintain monotonic order by popping larger dp values from the back. The front of the deque always stores the best next state, so dp[i] = price[i] + dp[deque.front]. Each index enters and leaves the deque once, giving linear time.
Recommended for interviews: Start with the DP recurrence to show understanding of the purchase rule and state transition. Then optimize the range minimum lookup. Interviewers typically expect the monotonic queue solution because it reduces the transition from O(n) to O(1), achieving O(n) overall while demonstrating strong knowledge of dynamic programming optimization techniques.
We define f[i] as the minimum number of coins needed to buy all fruits starting from the ith fruit. So 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].
In implementation, we calculate from back to front, and we can directly perform state transition on the array prices, which can save space.
The time complexity of the above method is O(n^2). Since the scale of n in this problem reaches 10^5, it will time out.
We observe the state transition equation and find that for each i, we need to find the minimum value of f[i + 1], f[i + 2], cdots, f[2i + 1], and as i decreases, the range of these values is also decreasing. This is actually finding the minimum value of a monotonically narrowing sliding window, and we can use a monotonic queue to optimize.
We calculate from back to front, maintain a monotonically increasing queue q, and the queue stores the index. If the head 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 head element. If i is not greater than (n - 1) / 2, then we can add prices[q[0] - 1] to prices[i - 1], and then add i to the tail of the queue. If the price of the fruit corresponding to the tail element of q is greater than or equal to prices[i - 1], then we dequeue the tail element until the price of the fruit corresponding to the tail element is less than prices[i - 1] or the queue is empty, and then add i to the tail of the queue.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array prices.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Dynamic Programming | O(n²) | O(n) | Useful for understanding the state transition and verifying correctness on small inputs |
| DP with Min Heap | O(n log n) | O(n) | When you want a simpler optimization using a priority queue |
| DP with Monotonic Queue | O(n) | O(n) | Optimal solution for large arrays where sliding window minimum is required |
【每日一题】LeetCode 2969. Minimum Number of Coins for Fruits II • Huifeng Guan • 253 views views
Watch 1 more video solutions →Practice Minimum Number of Coins for Fruits II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor