Minimum Number of Coins for Fruits - Video Solutions
2944. Minimum Number of Coins for Fruits
Minimum Number of Coins for Fruits - Video Solution
Watch 8 video solutions for Minimum Number of Coins for Fruits, a medium level problem involving Array, Dynamic Programming, Queue. This walkthrough by Ayush Rao has 1,923 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
ithfruit atprices[i]coins, you can get any number of the nextifruits 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.
Example 1:
Input: prices = [3,1,2]
Output: 4
Explanation:
- Purchase the 1st fruit with
prices[0] = 3coins, you are allowed to take the 2nd fruit for free. - Purchase the 2nd fruit with
prices[1] = 1coin, 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] = 1coin, you are allowed to take the 2nd fruit for free. - Take the 2nd fruit for free.
- Purchase the 3rd fruit for
prices[2] = 1coin, 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] = 26coin, you are allowed to take the 2nd fruit for free. - Take the 2nd fruit for free.
- Purchase the 3rd fruit for
prices[2] = 6coin, 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] = 7coin, 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 <= 10001 <= prices[i] <= 105
Approach Overview
Problem Overview: You are given an array prices where prices[i] represents the cost of buying the i-th fruit. When you buy fruit i, you can take the next i fruits for free. The goal is to buy fruits in a way that covers the entire array while minimizing the total number of coins spent.
Approach 1: Greedy with Priority Queue (O(n log n) time, O(n) space)
This method treats each purchase as a decision point and uses a min-heap to track the cheapest valid way to reach future fruits. While iterating through the array, push possible purchase states into a priority queue storing the total cost and the farthest index the purchase can cover. If the current index exceeds the coverage of the cheapest state, remove it from the heap. The smallest accumulated cost always represents the best way to cover the current fruit. This greedy strategy works because the heap maintains the minimum cost among all active purchase options.
Approach 2: Dynamic Programming with Monotonic Queue (O(n) time, O(n) space)
Define dp[i] as the minimum coins needed starting from fruit i. Buying fruit i costs prices[i] and allows you to skip to any position between i+1 and i+i+1. The recurrence becomes dp[i] = prices[i] + min(dp[j]) for all reachable j. Computing this naively costs O(n²), so maintain a sliding minimum using a monotonic queue. Process indices from right to left and keep the deque increasing by dp values, which lets you query the minimum transition in O(1). This transforms the dynamic programming transition into a linear-time solution.
Both solutions rely heavily on efficient range minimum tracking using structures like a heap (priority queue) or a monotonic queue. The DP formulation also demonstrates a classic optimization pattern in dynamic programming where a sliding window minimum removes nested loops.
Recommended for interviews: The dynamic programming approach with a monotonic queue is the expected optimal solution. It reduces the naive transition from O(n²) to O(n) while keeping the logic clean and deterministic. Starting with the basic DP recurrence shows understanding of the problem structure, and then optimizing it with a deque demonstrates strong algorithmic skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Priority Queue | O(n log n) | O(n) | Useful when modeling the problem as active purchase ranges and selecting the cheapest valid state using a heap |
| Dynamic Programming + Monotonic Queue | O(n) | O(n) | Best choice for interviews and large inputs where the DP transition needs fast sliding window minimum queries |