Problem

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 theminimum number of coins needed to acquire all the fruits.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8

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 <= 10^5
  • 1 <= prices[i] <= 10^5

Solution

Method 1 – Dynamic Programming (Sliding Window)

Intuition

To minimize coins, 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 sliding window helps efficiently track the minimum cost for each range.

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 and buying fruit j covers fruit i, update dp[i].
    • Use a sliding window to optimize the range updates.
  3. The answer is dp[n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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 + i >= i) {
                    dp[i] = min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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+i >= i {
                if dp[j]+prices[i-1] < dp[i] {
                    dp[i] = dp[j]+prices[i-1]
                }
            }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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+i >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + prices[i-1]);
                }
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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+i >= i) {
                    dp[i] = minOf(dp[i], dp[j] + prices[i-1])
                }
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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+i >= i:
                    dp[i] = min(dp[i], dp[j] + prices[i-1])
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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+i >= i {
                    dp[i] = dp[i].min(dp[j] + prices[i-1]);
                }
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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+i >= i) {
                    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.