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²).

Description Hints 7 Solution Video 17:40

2969. Minimum Number of Coins for Fruits II

Hard49.2% acceptancePremium elsewhere, free here

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 i^th fruit.

The fruit market has the following offer:

If you purchase the i^th 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 1^st fruit with 3 coins, and you are allowed to take the 2^nd fruit for free.
- Purchase the 2^nd fruit with 1 coin, and you are allowed to take the 3^rd fruit for free.
- Take the 3^rd fruit for free.
Note that even though you were allowed to take the 2^nd 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 1^st fruit with 1 coin, and you are allowed to take the 2^nd fruit for free.
- Take the 2^nd fruit for free.
- Purchase the 3^rd fruit for 1 coin, and you are allowed to take the 4^th fruit for free.
- Take the 4^t^h 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 <= 10⁵
1 <= prices[i] <= 10⁵

Topics

Hints open one at a time

Hint 1

Use DP + Fenwick tree.

Hint 2

There is another creative solution using multiset instead of Fenwick.

Hint 3

Imagine we want to calculate dp[i] which is the answer to the problem for the first i fruits.

Hint 4

If we buy l^th fruit from the set of indices: [(i + 1) / 2, (i + 1) / 2 + 1, (i + 1) / 2 + 2, ..., i - 1], then we can get fruits l + 1, l + 2, ..., i for free.

Hint 5

We just need to get all the first l - 1 fruits as well and the minimum price for that, is dp[l - 1].

Hint 6

So at the index i, we are looking for such an index l that dp[l - 1] + prices[l] is as minimum as possible.

Hint 7

We can store these values in a multiset and update the values in it.

17:40

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,1,2]

Input

[1,10,1,1]

Your code is saved on this device.Solution