Minimum Number of Coins for Fruits

Problem

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:

• If you purchase the 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.

Examples

Example 1

Input: prices = [3,1,2]

Output: 4

Explanation:

  * Purchase the 1st fruit with `prices[0] = 3` coins, you are allowed to take the 2nd fruit for free.
  * Purchase the 2nd fruit with `prices[1] = 1` coin, you are allowed to take the 3rd fruit for free.
  * 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:

  * Purchase the 1st fruit with `prices[0] = 1` coin, you are allowed to take the 2nd fruit for free.
  * Take the 2nd fruit for free.
  * Purchase the 3rd fruit for `prices[2] = 1` coin, you are allowed to take the 4th fruit for free.
  * Take the 4th fruit for free.

Example 3

Input: prices = [26,18,6,12,49,7,45,45]

Output: 39

Explanation:

  * Purchase the 1st fruit with `prices[0] = 26` coin, you are allowed to take the 2nd fruit for free.
  * Take the 2nd fruit for free.
  * Purchase the 3rd fruit for `prices[2] = 6` coin, you are allowed to take the 4th, 5th and 6th (the next three) fruits for free.
  * Take the 4th fruit for free.
  * Take the 5th fruit for free.
  * Purchase the 6th fruit with `prices[5] = 7` coin, you are allowed to take the 8th and 9th fruit for free.
  * Take the 7th fruit for free.
  * Take the 8th 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 <= 1000
• 1 <= prices[i] <= 10^5

Solution

Method 1 – Dynamic Programming (Monotonic Queue)

Intuition

To minimize coins, we use DP where dp[i] is the minimum coins to buy up to fruit i. For each fruit, buying it lets us get the next i fruits for free, so we update the DP accordingly. A monotonic queue can optimize the range updates.

Approach

1. Initialize dp[0] = 0 and dp[i] = inf for all other i.
2. For each fruit i from 1 to n:
   • For each possible previous fruit j where j < i, if buying fruit j covers fruit i, update dp[i].
   • Use a monotonic queue to keep track of minimum dp values for efficient updates.
3. The answer is dp[n].

Code

C++

class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = max(0, i-i); j < i; ++j) {
                if (j + j >= i-1) {
                    dp[i] = min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
};

Go

func minimumCoins(prices []int) int {
    n := len(prices)
    dp := make([]int, n+1)
    for i := range dp { dp[i] = 1<<30 }
    dp[0] = 0
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if j+j >= i-1 {
                if dp[j]+prices[i-1] < dp[i] {
                    dp[i] = dp[j]+prices[i-1]
                }
            }
        }
    }
    return dp[n]
}

Java

class Solution {
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (j+j >= i-1) {
                    dp[i] = Math.min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
}

Kotlin

class Solution {
    fun minimumCoins(prices: IntArray): Int {
        val n = prices.size
        val dp = IntArray(n+1) { Int.MAX_VALUE }
        dp[0] = 0
        for (i in 1..n) {
            for (j in 0 until i) {
                if (j+j >= i-1) {
                    dp[i] = minOf(dp[i], dp[j] + prices[i-1])
                }
            }
        }
        return dp[n]
    }
}

Python

class Solution:
    def minimumCoins(self, prices: list[int]) -> int:
        n: int = len(prices)
        dp: list[int] = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for j in range(i):
                if j+j >= i-1:
                    dp[i] = min(dp[i], dp[j] + prices[i-1])
        return dp[n]

Rust

impl Solution {
    pub fn minimum_coins(prices: Vec<i32>) -> i32 {
        let n = prices.len();
        let mut dp = vec![i32::MAX; n+1];
        dp[0] = 0;
        for i in 1..=n {
            for j in 0..i {
                if j+j >= i-1 {
                    dp[i] = dp[i].min(dp[j] + prices[i-1]);
                }
            }
        }
        dp[n]
    }
}

TypeScript

class Solution {
    minimumCoins(prices: number[]): number {
        const n = prices.length;
        const dp = new Array(n+1).fill(Infinity);
        dp[0] = 0;
        for (let i = 1; i <= n; ++i) {
            for (let j = 0; j < i; ++j) {
                if (j+j >= i-1) {
                    dp[i] = Math.min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
}

Complexity

• ⏰ Time complexity: O(n^2), as we check all previous states for each fruit.
• 🧺 Space complexity: O(n), for the DP array.