LeetCode 2944 - Minimum Number of Coins for Fruits

This problem asks us to determine the minimum number of coins required to acquire all fruits in a market where buying a fruit grants a special reward. You are given a 0-indexed array prices, where prices[i] represents the cost of purchasing the (i + 1)th fruit.

leetcodemediumarraydynamic-programmingqueueheap-(priority-queue)monotonic-queue

LeetCode Problem 2944

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Queue, Heap (Priority Queue), Monotonic Queue

Solution

Problem Understanding

This problem asks us to determine the minimum number of coins required to acquire all fruits in a market where buying a fruit grants a special reward.

You are given a 0-indexed array prices, where prices[i] represents the cost of purchasing the (i + 1)th fruit. The important twist is that purchasing fruit i + 1 unlocks a reward: you may take any number of the next i fruits for free.

This reward rule is easy to misread, so let us restate it carefully.

If you purchase fruit at index i, you pay prices[i], and then you may freely take fruits in the range:

[i + 1, 2 * i + 1]

For example:

  • Buying fruit 1 (index 0) gives access to the next 0 fruits, which means no additional reward.
  • Buying fruit 2 (index 1) allows taking the next 1 fruit for free.
  • Buying fruit 3 (index 2) allows taking the next 2 fruits for free.
  • Buying fruit 6 (index 5) allows taking the next 5 fruits for free.

A key subtlety is that even if a fruit can be taken for free, you are still allowed to purchase it intentionally. Doing so may be beneficial because purchasing that fruit unlocks its own reward, potentially covering many future fruits more efficiently.

The goal is to compute the minimum total number of coins needed to obtain every fruit, whether by paying or taking them for free.

Understanding the Constraints

The constraints are:

  • 1 <= prices.length <= 1000
  • 1 <= prices[i] <= 10^5

The array size is relatively small, only up to 1000, which means an O(n²) dynamic programming solution is acceptable. However, brute force exponential search would quickly become infeasible.

Because rewards create overlapping future states, this problem strongly suggests dynamic programming. Each decision affects which future fruits are covered, and many subproblems repeat.

Important Edge Cases

A naive implementation can fail on several important scenarios.

When there is only one fruit, the answer must simply be its price because there are no future rewards to exploit.

If buying an early fruit covers many later fruits, we still need to consider whether purchasing one of those free fruits leads to an even better total cost because of additional rewards.

When prices are highly uneven, greedily choosing the cheapest fruit or always taking free fruits can fail. A more expensive purchase may unlock enough future coverage to reduce overall cost.

The problem guarantees:

  • The array is non-empty.
  • All prices are positive integers.
  • Every fruit must eventually be acquired.

This means we do not need to handle invalid inputs or negative costs.

Approaches

Brute Force Approach

A brute force solution would recursively try every valid decision.

At any fruit index, we have two conceptual possibilities:

  1. Purchase the fruit and gain its reward coverage.
  2. Take the fruit for free if a previous purchase allows it.

The recursion would branch repeatedly, exploring every possible combination of purchases and free acquisitions.

For each purchased fruit, we would recursively compute the minimum cost for the remaining uncovered fruits. Since multiple purchase combinations can overlap heavily, the same subproblems would be recomputed many times.

This approach is correct because it exhaustively evaluates every possible strategy and chooses the minimum cost. However, it becomes prohibitively slow because the number of possible purchase combinations grows exponentially.

Key Insight for an Optimal Solution

The key observation is that the problem naturally forms a dynamic programming transition.

Let:

dp[i] = minimum coins needed to acquire fruits from index i onward

Suppose we decide to purchase fruit i.

After paying prices[i], we may freely take up to the next i + 1 fruits.

That means the next fruit we must actively consider lies somewhere after:

2 * i + 1

More precisely, after purchasing fruit i, the next uncovered fruit can begin from:

i + 1 through 2*i + 2

We want the cheapest future option.

This leads to the recurrence:

dp[i] = prices[i] + min(dp[j])

where:

j ∈ [i + 1, 2*i + 2]

If j >= n, then no fruits remain and the cost is 0.

A straightforward DP implementation would scan the range every time, producing O(n²) time.

We can optimize this using a monotonic queue (deque) to efficiently maintain the minimum dp value inside the valid sliding window.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2ⁿ) O(n) Explores all purchase combinations recursively
Optimal Dynamic Programming + Monotonic Queue O(n) O(n) Uses deque to maintain sliding minimum efficiently

Algorithm Walkthrough

We solve the problem using bottom up dynamic programming with a monotonic deque.

Step 1: Define the DP State

Let:

dp[i]

represent the minimum cost needed to acquire all fruits starting from index i.

We also define:

dp[n] = 0

because if we have already processed all fruits, no more coins are required.

Step 2: Process from Right to Left

We compute states backwards.

This is important because:

dp[i]

depends on future states.

When calculating dp[i], all future dp[j] values are already known.

Step 3: Understand the Transition

If we buy fruit i, we pay:

prices[i]

Buying fruit i covers fruits:

[i + 1, 2*i + 1]

So the next uncovered fruit could start at:

j ∈ [i + 1, 2*i + 2]

Thus:

dp[i] =
prices[i] + min(dp[j])

for all valid j.

Step 4: Maintain the Minimum Efficiently

Instead of scanning every valid j, we maintain a monotonic deque.

The deque stores candidate indices whose dp values are increasing.

This gives us:

minimum dp[j]

in constant time from the front of the deque.

We remove indices that fall outside the valid transition window.

We also remove worse candidates from the back so the deque remains monotonic.

Step 5: Compute the Answer

After processing every index:

dp[0]

contains the minimum number of coins needed to acquire all fruits.

Why it works

The algorithm works because dynamic programming guarantees optimal substructure.

For every fruit i, we consider the cost of purchasing it and then optimally solving the remaining uncovered fruits. Since every future subproblem dp[j] has already been computed optimally, taking the minimum among them guarantees the best continuation.

The monotonic deque preserves the invariant that the front always contains the smallest valid dp value for the current transition range. Therefore, each state computes the exact recurrence efficiently without losing correctness.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [0] * (n + 1)

        monotonic_queue = deque()
        monotonic_queue.append((n, 0))

        for i in range(n - 1, -1, -1):
            max_reach = min(n, 2 * i + 2)

            while monotonic_queue and monotonic_queue[0][0] > max_reach:
                monotonic_queue.popleft()

            dp[i] = prices[i] + monotonic_queue[0][1]

            while monotonic_queue and monotonic_queue[-1][1] >= dp[i]:
                monotonic_queue.pop()

            monotonic_queue.append((i, dp[i]))

        return dp[0]

Implementation Explanation

We begin by initializing the DP array of size n + 1.

The extra position:

dp[n]

represents the base case where no fruits remain to be purchased.

We maintain a deque storing:

(index, dp value)

The deque is monotonic in increasing order of dp values.

We process fruits from right to left so that all future DP values are already computed when needed.

For each fruit i, we calculate:

max_reach = 2*i + 2

This determines the farthest next starting position after buying fruit i.

We remove invalid states from the front of the deque because they are outside the allowable transition range.

The front element always contains the minimum valid future cost.

Then:

dp[i] = prices[i] + minimum_future_cost

Finally, we maintain monotonic order by removing larger DP values from the back before inserting the current state.

This guarantees efficient constant time minimum lookup.

Go Solution

func minimumCoins(prices []int) int {
	n := len(prices)
	dp := make([]int, n+1)

	type Pair struct {
		index int
		cost  int
	}

	deque := []Pair{{n, 0}}

	for i := n - 1; i >= 0; i-- {
		maxReach := min(n, 2*i+2)

		for len(deque) > 0 && deque[0].index > maxReach {
			deque = deque[1:]
		}

		dp[i] = prices[i] + deque[0].cost

		for len(deque) > 0 &&
			deque[len(deque)-1].cost >= dp[i] {
			deque = deque[:len(deque)-1]
		}

		deque = append(deque, Pair{i, dp[i]})
	}

	return dp[0]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Go-specific Implementation Differences

The Go implementation follows the same logic as Python, but uses a slice to simulate the deque.

Instead of tuples, we define a Pair struct containing:

index
cost

Go does not provide a built-in deque structure, so we simulate popping from the front using slicing:

deque = deque[1:]

Since all values fit comfortably inside Go's int range for the problem constraints, integer overflow is not a concern.

Nil versus empty slices is also not an issue because we explicitly initialize the deque with:

{n, 0}

ensuring it is never empty when accessed.

Worked Examples

Example 1

Input:

prices = [3,1,2]

We process from right to left.

i price valid range minimum future dp dp[i] deque after update
2 2 [3] 0 2 [(3,0),(2,2)]
1 1 [2,3] 0 1 [(3,0),(1,1)]
0 3 [1] 1 4 [(1,1),(0,4)]

Final answer:

dp[0] = 4

Example 2

Input:

prices = [1,10,1,1]
i price valid range minimum future dp dp[i]
3 1 [4] 0 1
2 1 [3,4] 0 1
1 10 [2,3] 1 11
0 1 [1] 1 2

Final answer:

2

Optimal strategy:

  • Buy fruit 1
  • Take fruit 2 free
  • Buy fruit 3
  • Take fruit 4 free

Example 3

Input:

prices = [26,18,6,12,49,7,45,45]
i price dp[i]
7 45 45
6 45 45
5 7 7
4 49 49
3 12 19
2 6 13
1 18 31
0 26 39

Final answer:

39

Optimal purchases:

1st fruit → 3rd fruit → 6th fruit

Total:

26 + 6 + 7 = 39

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index enters and leaves the deque at most once
Space O(n) DP array and deque storage

The key reason the solution runs in linear time is that every index is inserted into the monotonic queue exactly once and removed at most once. Although there are nested while loops, the total work across all iterations remains linear because no element is repeatedly processed.

The DP array requires O(n) memory, and the deque also stores at most n + 1 states.

Test Cases

sol = Solution()

assert sol.minimumCoins([3, 1, 2]) == 4  # Example 1
assert sol.minimumCoins([1, 10, 1, 1]) == 2  # Example 2
assert sol.minimumCoins([26, 18, 6, 12, 49, 7, 45, 45]) == 39  # Example 3

assert sol.minimumCoins([5]) == 5  # Single fruit
assert sol.minimumCoins([1, 1]) == 2  # Must buy both
assert sol.minimumCoins([1, 1, 1]) == 2  # Buy first and second

assert sol.minimumCoins([100, 1, 1, 1]) == 101  # Expensive first fruit
assert sol.minimumCoins([1, 100, 1, 100, 1]) == 3  # Strategic purchases

assert sol.minimumCoins([5, 4, 3, 2, 1]) == 8  # Decreasing prices
assert sol.minimumCoins([1, 2, 3, 4, 5]) == 4  # Increasing prices

assert sol.minimumCoins([10] * 1000) > 0  # Large input stress test

Test Summary

Test Why
[3,1,2] Verifies first example
[1,10,1,1] Verifies free fruit strategy
[26,18,6,12,49,7,45,45] Verifies complex optimal path
[5] Smallest input
[1,1] Minimal multiple fruit case
[1,1,1] Free fruit chaining
[100,1,1,1] Expensive early purchase
[1,100,1,100,1] Tests non-greedy decisions
[5,4,3,2,1] Decreasing costs
[1,2,3,4,5] Increasing costs
Large repeated values Performance stress test

Edge Cases

Single Fruit

If the input contains only one fruit, there are no rewards to exploit because there are no future fruits.

Example:

[5]

The only valid answer is 5.

This case can cause indexing mistakes in implementations that assume future states exist. Our DP handles it naturally because:

dp[n] = 0

serves as the base case.

Purchasing a Free Fruit Intentionally

A fruit that can be taken for free may still be worth purchasing.

Example:

[3,1,2]

Fruit 2 can be taken for free after buying fruit 1, but purchasing fruit 2 unlocks fruit 3 for free, producing a cheaper total.

A greedy strategy would miss this. Our DP correctly explores both possibilities implicitly through optimal transitions.

Large Reward Coverage

Some fruits may cover almost all remaining fruits.

Example:

[1,100,100,100]

Buying the third fruit can potentially cover many future positions.

This can create off-by-one bugs in range calculations. Our implementation safely caps coverage using:

min(n, 2 * i + 2)

ensuring indices never exceed bounds.

Highly Uneven Prices

A locally expensive fruit may still be optimal if it unlocks strong future rewards.

Example:

[1,100,1,100,1]

Greedy intuition can fail here because minimizing immediate cost is not equivalent to minimizing total cost.

Dynamic programming guarantees the globally optimal answer by evaluating every valid continuation efficiently.