Minimum Number of Coins for Fruits

Med

#2624Time: O(n^2) - We have a nested loop structure. The outer loop runs `n` times (for `i` from 1 to `n`), and the inner loop runs up to `i/2` times (for `k` from `ceil(i/2)` to `i`). This results in a total time complexity proportional to the sum of `i/2` from `i=1` to `n`, which is `O(n^2)`.Space: O(n) - We use a DP array of size `n+1` to store the minimum costs.

Patterns

Dynamic Programming

Data structures

Array Heap (Priority Queue)Queue Monotonic Queue

Prompt

You are given an 0-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the (i + 1)^th fruit.

The fruit market has the following reward for each fruit:

If you purchase the (i + 1)^th 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 - 1] coins to receive its reward.

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

Example 1:

Input: prices = [3,1,2]

Output: 4

Explanation:

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

Note that even though you could take the 2^nd fruit for free as a reward of buying 1^st 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 1^st fruit with prices[0] = 1 coin, you are allowed to take the 2^nd fruit for free.
Take the 2^nd fruit for free.
Purchase the 3^rd fruit for prices[2] = 1 coin, you are allowed to take the 4^th fruit for free.
Take the 4^t^h fruit for free.

Example 3:

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

Output: 39

Explanation:

Purchase the 1^st fruit with prices[0] = 26 coin, you are allowed to take the 2^nd fruit for free.
Take the 2^nd fruit for free.
Purchase the 3^rd fruit for prices[2] = 6 coin, you are allowed to take the 4^th, 5^th and 6^th (the next three) fruits for free.
Take the 4^t^h fruit for free.
Take the 5^t^h fruit for free.
Purchase the 6^th fruit with prices[5] = 7 coin, you are allowed to take the 8^th and 9^th fruit for free.
Take the 7^t^h fruit for free.
Take the 8^t^h fruit for free.

Note that even though you could take the 6^th fruit for free as a reward of buying 3^rd fruit, you purchase it to receive its reward, which is more optimal.

Constraints:

1 <= prices.length <= 1000
1 <= prices[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This problem exhibits optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. We can define a DP state dp[i] as the minimum cost to acquire the first i fruits. Our goal is to find dp[n], the minimum cost for all n fruits.

The base case is dp[0] = 0, as acquiring no fruits costs nothing.

To compute dp[i], we must ensure fruit i is acquired. This can happen if we buy fruit i, or if we get it for free from a prior purchase. We can generalize this by considering that to acquire fruit i, we must have bought some fruit k (where 1 <= k <= i) that 'covers' fruit i. Buying fruit k (at index k-1) gives fruits k+1 through 2k for free. Thus, fruit k covers fruit i if k=i or k+1 <= i <= 2k. The latter condition simplifies to ceil(i/2) <= k <= i-1.

So, to find dp[i], we can take the minimum over all valid choices of k from ceil(i/2) to i. For each such k, the cost is the price of fruit k (prices[k-1]) plus the minimum cost to acquire fruits 1 to k-1 (dp[k-1]). This gives the recurrence relation:

dp[i] = min_{k=ceil(i/2)}^{i} (dp[k-1] + prices[k-1])

We can implement this by iterating i from 1 to n and, for each i, iterating k through its valid range to find the minimum cost.

Algorithm

Create a DP array dp of size n+1, where n is the number of fruits.
Initialize dp[0] = 0, and other elements to a large value.
Iterate i from 1 to n to compute dp[i], the minimum cost to acquire fruits 1 through i.
For each i, calculate the cost by considering all possible fruits k (from ceil(i/2) to i) that could be purchased to cover fruit i.
The cost of purchasing fruit k is prices[k-1], and we must have already acquired fruits 1 to k-1 with a minimum cost of dp[k-1]. The total cost for this choice is dp[k-1] + prices[k-1].
Update dp[i] with the minimum cost found among all valid choices of k.
The final answer is dp[n].

Walkthrough

We use a bottom-up dynamic programming approach. Let dp[i] be the minimum cost to obtain the first i fruits (using 1-based indexing for fruits, so i ranges from 1 to n). The size of our dp array will be n+1.

Initialization: dp[0] = 0. All other dp values can be initialized to infinity.
Recurrence: To calculate dp[i], we consider all possible fruits k we could have purchased that would cover fruit i. A purchase of fruit k covers fruit i if i is k itself, or if i is one of the free fruits obtained from buying k (i.e., k+1 <= i <= 2k). This gives a range for k from ceil(i/2) to i. For any such k, the total cost would be the cost to acquire fruits up to k-1 (dp[k-1]) plus the cost of fruit k (prices[k-1]). We take the minimum over all these possibilities.

dp[i] = min(dp[k-1] + prices[k-1]) for k in [ceil(i/2), i]

Final Answer: The minimum cost to acquire all n fruits is dp[n].

Here is the Java implementation:

1class Solution {2    public int minimumCoins(int[] prices) {3        int n = prices.length;4        int[] dp = new int[n + 1];5        // dp[i] = min cost to acquire first i fruits (1-based index)6        7        dp[0] = 0;8        9        for (int i = 1; i <= n; i++) {10            dp[i] = Integer.MAX_VALUE;11            // To acquire fruit i, we must buy some fruit k (1-based)12            // such that buying k covers i.13            // This means k=i, or k+1 <= i <= 2k.14            // The range for k is [ceil(i/2), i].15            // For positive integers, ceil(i/2) is (i+1)/2 using integer division.16            int start_k = (i + 1) / 2;17            for (int k = start_k; k <= i; k++) {18                // Cost of buying fruit k is prices[k-1].19                // We must have acquired fruits 1...k-1, which costs dp[k-1].20                // Total cost for this choice is dp[k-1] + prices[k-1].21                dp[i] = Math.min(dp[i], dp[k - 1] + prices[k - 1]);22            }23        }24        25        return dp[n];26    }27}

Complexity

Time

O(n^2) - We have a nested loop structure. The outer loop runs `n` times (for `i` from 1 to `n`), and the inner loop runs up to `i/2` times (for `k` from `ceil(i/2)` to `i`). This results in a total time complexity proportional to the sum of `i/2` from `i=1` to `n`, which is `O(n^2)`.

Space

O(n) - We use a DP array of size `n+1` to store the minimum costs.

Trade-offs

Pros

Relatively straightforward to understand and implement based on the DP recurrence relation.
Correctly solves the problem for the given constraints.

Cons

The time complexity is quadratic, which can be slow for larger constraints (though it passes for n=1000).

The O(n^2) DP approach can be optimized by observing the nature of the recurrence relation: dp[i] = min_{k=ceil(i/2)}^{i} (dp[k-1] + prices[k-1])

Let's define a cost function cost(k) = dp[k-1] + prices[k-1]. The problem then becomes finding the minimum value of cost(k) in a window [ceil(i/2), i]. As we increment i, this window slides and expands. This is a classic sliding window minimum problem, which can be solved efficiently in linear time using a double-ended queue (deque).

The deque will store indices k from the current window. It will be maintained in two ways: the indices themselves will be in increasing order, and their corresponding cost(k) values will also be in increasing order. This structure allows us to find the minimum cost(k) in the window (which will always be at the front of the deque) in O(1) time.

For each step i, we first remove indices from the front of the deque that are no longer in the current window. Then, we find dp[i] by comparing the minimum from the deque with the cost of buying fruit i. Finally, we add i to the deque, maintaining the sorted-cost property by removing any elements from the back that have a higher or equal cost.

Algorithm

Create a DP array dp of size n+1 and a deque.
Initialize dp[0] = 0.
Iterate i from 1 to n.
In each iteration, first, prune the deque by removing indices k from the front that are no longer in the current window [ceil(i/2), i].
The minimum cost from the choices k in [ceil(i/2), i-1] can be found in O(1) from the front of the deque.
Calculate the cost for choosing k=i, which is dp[i-1] + prices[i-1].
dp[i] is the minimum of these two options.
Finally, add i to the deque, maintaining the property that costs associated with indices in the deque are monotonically increasing. This may involve removing elements from the back.
The result is dp[n].

Walkthrough

This approach optimizes the O(n^2) DP solution to O(n) time using a deque to maintain the sliding window minimum.

DP State: dp[i] is the minimum cost to acquire fruits 1...i.
Optimization: The calculation dp[i] = min_{k=ceil(i/2)}^{i} (dp[k-1] + prices[k-1]) is a range minimum query. We use a deque to find this minimum in amortized O(1) time.

Algorithm Steps:

Initialize dp array of size n+1 with dp[0] = 0.
Initialize an empty ArrayDeque to store indices k.
Loop i from 1 to n: a. Define the window start start_k = (i + 1) / 2. b. Remove indices from the deque's front that are less than start_k. c. Get the minimum cost from the window [start_k, i-1]. This corresponds to cost(deque.peekFirst()) if the deque is not empty. d. Calculate the cost for buying fruit i: cost(i) = dp[i-1] + prices[i-1]. e. dp[i] is the minimum of the costs from steps c and d. f. To add i to the deque, first remove indices from the back of the deque whose associated cost is greater than or equal to cost(i). Then, add i to the back.
Return dp[n].

Here is the Java implementation:

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public int minimumCoins(int[] prices) {6        int n = prices.length;7        int[] dp = new int[n + 1];8        // Deque stores indices k (1-based) for the sliding window minimum.9        Deque<Integer> deque = new ArrayDeque<>();10        11        dp[0] = 0;12        13        for (int i = 1; i <= n; i++) {14            int start_k = (i + 1) / 2;15            16            // Remove indices from the front that are out of the window [start_k, i].17            while (!deque.isEmpty() && deque.peekFirst() < start_k) {18                deque.pollFirst();19            }20            21            // Cost from buying a fruit j in [start_k, i-1]22            int minPrevCost = Integer.MAX_VALUE;23            if (!deque.isEmpty()) {24                int k = deque.peekFirst();25                minPrevCost = dp[k - 1] + prices[k - 1];26            }27            28            // Cost from buying fruit i itself.29            int costOfBuyingI = dp[i - 1] + prices[i - 1];30            31            dp[i] = Math.min(minPrevCost, costOfBuyingI);32            33            // Add current index i to the deque, maintaining the increasing cost property.34            while (!deque.isEmpty()) {35                int k = deque.peekLast();36                if (dp[k - 1] + prices[k - 1] >= costOfBuyingI) {37                    deque.pollLast();38                } else {39                    break;40                }41            }42            deque.offerLast(i);43        }44        45        return dp[n];46    }47}

Complexity

Time

O(n) - The main loop runs `n` times. Each index `i` is added to and removed from the deque at most once. Therefore, all operations inside the loop take amortized `O(1)` time, leading to a total linear time complexity.

Space

O(n) - We use a DP array of size `n+1` and a deque that can store up to `n` indices in the worst case.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Optimal solution for the problem.

Cons

The implementation is more complex than the basic DP approach.
Requires knowledge of the sliding window minimum technique using a deque.

Solutions

Solution

1class Solution {2private3  int[] prices;4private5  int[] f;6private7  int n;8public9  int minimumCoins(int[] prices) {10    n = prices.length;11    f = new int[n + 1];12    this.prices = prices;13    return dfs(1);14  }15private16  int dfs(int i) {17    if (i * 2 >= n) {18      return prices[i - 1];19    }20    if (f[i] == 0) {21      f[i] = 1 << 30;22      for (int j = i + 1; j <= i * 2 + 1; ++j) {23        f[i] = Math.min(f[i], prices[i - 1] + dfs(j));24      }25    }26    return f[i];27  }28}

1class Solution {2public:3  int minimumCoins(vector<int> &prices) {4    int n = prices.size();5    int f[n + 1];6    memset(f, 0x3f, sizeof(f));7    function<int(int)> dfs = [&](int i) {8      if (i * 2 >= n) {9        return prices[i - 1];10      }11      if (f[i] == 0x3f3f3f3f) {12        for (int j = i + 1; j <= i * 2 + 1; ++j) {13          f[i] = min(f[i], prices[i - 1] + dfs(j));14        }15      }16      return f[i];17    };18    return dfs(1);19  }20};

1class Solution:2    def minimumCoins(self, prices: List[int]) -> int: @ cache def dfs(i: int) -> int: if i * 2 >= len(prices): return prices[i - 1] return prices[i - 1] + min(dfs(j) for j in range(i + 1, i * 2 + 2)) return dfs(1)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int[] prices;4private5  int[] f;6private7  int n;8public9  int minimumCoins(int[] prices) {10    n = prices.length;11    f = new int[n + 1];12    this.prices = prices;13    return dfs(1);14  }15private16  int dfs(int i) {17    if (i * 2 >= n) {18      return prices[i - 1];19    }20    if (f[i] == 0) {21      f[i] = 1 << 30;22      for (int j = i + 1; j <= i * 2 + 1; ++j) {23        f[i] = Math.min(f[i], prices[i - 1] + dfs(j));24      }25    }26    return f[i];27  }28}

1class Solution {2public:3  int minimumCoins(vector<int> &prices) {4    int n = prices.size();5    int f[n + 1];6    memset(f, 0x3f, sizeof(f));7    function<int(int)> dfs = [&](int i) {8      if (i * 2 >= n) {9        return prices[i - 1];10      }11      if (f[i] == 0x3f3f3f3f) {12        for (int j = i + 1; j <= i * 2 + 1; ++j) {13          f[i] = min(f[i], prices[i - 1] + dfs(j));14        }15      }16      return f[i];17    };18    return dfs(1);19  }20};

1class Solution:2    def minimumCoins(self, prices: List[int]) -> int: @ cache def dfs(i: int) -> int: if i * 2 >= len(prices): return prices[i - 1] return prices[i - 1] + min(dfs(j) for j in range(i + 1, i * 2 + 2)) return dfs(1)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.