Minimum Number of Coins for Fruits

Medium
1451.

Minimum Number of Coins for Fruits

Minimum Number of Coins for Fruits is a medium coding problem on arrays, dynamic programming and monotonic queue, asked in Amazon and Microsoft interviews.

A fruit stall at the CodeKairo meetup lines up n fruits, numbered from 1. Buying the i-th fruit costs prices[i - 1] coins and comes with a reward: the next i fruits (numbers i + 1 to 2i) are yours for free.

You may still pay for a fruit you could take for free — buying it earns its own reward.

Return the minimum number of coins needed to end up with every fruit.

Example 1

Input
prices = [5,2,8]
Output
7
Explanation
Buy fruit 1 (5 coins) and fruit 2 is free; buy fruit 2 anyway (2 coins) so fruits 3 and 4 are free.

Example 2

Input
prices = [1,10,1,1]
Output
2
Explanation
Buy fruit 1 (fruit 2 free), then buy fruit 3 (fruit 4 free).

Example 3

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

Constraints

  • 1 <= prices.length <= 1000
  • 1 <= prices[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @return {number}
 */
var minimumCoins = function(prices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Coins for Fruits — Problem & Solution

Minimum Number of Coins for Fruits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Number of Coins for Fruits is a medium coding problem on arrays, dynamic programming and monotonic queue, asked in Amazon and Microsoft interviews.

Problem statement

A fruit stall at the CodeKairo meetup lines up n fruits, numbered from 1. Buying the i-th fruit costs prices[i - 1] coins and comes with a reward: the next i fruits (numbers i + 1 to 2i) are yours for free.

You may still pay for a fruit you could take for free — buying it earns its own reward.

Return the minimum number of coins needed to end up with every fruit.

Example 1

Input: prices = [5,2,8]
Output: 7
Explanation: Buy fruit 1 (5 coins) and fruit 2 is free; buy fruit 2 anyway (2 coins) so fruits 3 and 4 are free.

Example 2

Input: prices = [1,10,1,1]
Output: 2
Explanation: Buy fruit 1 (fruit 2 free), then buy fruit 3 (fruit 4 free).

Example 3

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

Constraints

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

Hints for Minimum Number of Coins for Fruits

  1. Hint 1

    Fruit 1 can never be free, so it is always bought.

  2. Hint 2

    After buying fruit i, fruits up to 2i are covered — the next fruit you must pay for is somewhere in i + 1 .. 2i + 1.

  3. Hint 3

    Let dp[i] be the cheapest cost to own fruits i..n given you buy fruit i: prices[i-1] + min(dp[j]) for j in i + 1 .. 2i + 1, with dp[n + 1] = 0.

How to solve Minimum Number of Coins for Fruits

Think of the purchases in increasing order. After buying fruit i, everything up to 2i is covered, so the next purchase can be any fruit from i + 1 to 2i + 1 — buying earlier than needed is allowed and sometimes cheaper.

Approach

  1. Create dp of size n + 2 with dp[n + 1] = 0 (nothing left to buy).
  2. For i from n down to 1: dp[i] = prices[i - 1] + min(dp[j]) over j from i + 1 to min(2i + 1, n + 1).
  3. Return dp[1], since fruit 1 must be bought.

Why it works

Sort the purchases of any valid plan. Consecutive purchases i < j must satisfy j <= 2i + 1, or fruit 2i + 1 would be neither bought nor covered (earlier purchases cover even less). Conversely, any chain starting at 1 where each step is at most 2i + 1 and the last purchase reaches n covers every fruit. The DP minimises over exactly these chains.

Complexity

  • Time — O(n^2) — a monotonic deque over the window brings it to O(n)
  • Space — O(n)

Pitfalls

  • Fruits are 1-indexed in the reward rule: fruit i frees i fruits, so index arithmetic on prices needs i - 1.
  • Greedily taking every free fruit is not optimal — paying for a cheap fruit can unlock a longer free run.
  • The window ends at 2i + 1, not 2i: that fruit is the first one not covered.

Reference solution

Python

from typing import List

def minimumCoins(prices: List[int]) -> int:
    n = len(prices)
    dp = [0] * (n + 2)
    for i in range(n, 0, -1):
        hi = min(2 * i + 1, n + 1)
        dp[i] = prices[i - 1] + min(dp[i + 1:hi + 1])
    return dp[1]

Java

public static int minimumCoins(int[] prices) {
    int n = prices.length;
    int[] dp = new int[n + 2];
    for (int i = n; i >= 1; i--) {
        int hi = Math.min(2 * i + 1, n + 1);
        int best = Integer.MAX_VALUE;
        for (int j = i + 1; j <= hi; j++) best = Math.min(best, dp[j]);
        dp[i] = prices[i - 1] + best;
    }
    return dp[1];
}

C++

int minimumCoins(vector<int>& prices) {
    int n = prices.size();
    vector<int> dp(n + 2, 0);
    for (int i = n; i >= 1; i--) {
        int hi = min(2 * i + 1, n + 1);
        int best = INT_MAX;
        for (int j = i + 1; j <= hi; j++) best = min(best, dp[j]);
        dp[i] = prices[i - 1] + best;
    }
    return dp[1];
}

JavaScript

var minimumCoins = function(prices) {
    var n = prices.length;
    var dp = new Array(n + 2).fill(0);
    for (var i = n; i >= 1; i--) {
        var hi = Math.min(2 * i + 1, n + 1);
        var best = Infinity;
        for (var j = i + 1; j <= hi; j++) if (dp[j] < best) best = dp[j];
        dp[i] = prices[i - 1] + best;
    }
    return dp[1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming