Skip to main content
Talentd

Minimum Number of Coins for Fruits II - Solution & Explanation

HardPremiumFree on FleetCodeArrayDynamic ProgrammingQueueHeap (Priority Queue)15 min read
Practice this problem

Problem Statement

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:

  • If you purchase the 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 <= 105
  • 1 <= prices[i] <= 105

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Dynamic ProgrammingO(n²)O(n)Useful for understanding the state transition and verifying correctness on small inputs
DP with Min HeapO(n log n)O(n)When you want a simpler optimization using a priority queue
DP with Monotonic QueueO(n)O(n)Optimal solution for large arrays where sliding window minimum is required

Video Solution

【每日一题】LeetCode 2969. Minimum Number of Coins for Fruits II • Huifeng Guan • 255 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Minimum Number of Coins for Fruits II easy or hard?
Minimum Number of Coins for Fruits II is classified as a Hard problem. The difficulty comes from recognizing the DP transition and optimizing the range minimum query using a monotonic queue or priority queue.
Minimum Number of Coins for Fruits II Python/Java solution
The solution uses dynamic programming with a sliding window minimum structure. Python implementations typically use collections.deque for the monotonic queue, while Java uses ArrayDeque. Both maintain candidate dp indices while iterating through the array.
How to solve Minimum Number of Coins for Fruits II in O(n)?
Compute DP from right to left where dp[i] = price[i] plus the minimum dp value among the next valid purchase positions. Maintain those candidate states in a monotonic deque that keeps dp values in increasing order. Remove indices that fall outside the sliding window and read the minimum from the front in O(1).
What is the best approach for Minimum Number of Coins for Fruits II?
The most efficient approach uses dynamic programming optimized with a monotonic queue. The DP state represents the minimum cost from a given index, and the deque maintains the minimum future cost within the allowed purchase window. This reduces the transition lookup to constant time and achieves O(n) total complexity.
Is Minimum Number of Coins for Fruits II asked at Google/Amazon/Meta?
Problems combining dynamic programming with sliding window optimization frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require maintaining a minimum over a moving range are common interview patterns.
What data structure is used in Minimum Number of Coins for Fruits II?
The optimal implementation uses a monotonic queue (deque) to maintain the minimum DP value inside a sliding window. A priority queue (min heap) can also be used as an intermediate optimization, though it increases complexity to O(n log n).
What is the time complexity of Minimum Number of Coins for Fruits II?
The optimal solution runs in O(n) time using dynamic programming with a monotonic queue. Each index is inserted and removed from the deque at most once. A heap-based alternative runs in O(n log n), while the naive DP approach takes O(n²).

Ready to solve this problem?

Practice Minimum Number of Coins for Fruits II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays