Minimum Number of Coins for Fruits - Solution & Explanation

Q: Is Minimum Number of Coins for Fruits easy or hard?

Minimum Number of Coins for Fruits is generally rated Medium difficulty. The base dynamic programming idea is straightforward, but recognizing the sliding window minimum optimization with a monotonic queue makes the problem more challenging.

Q: Minimum Number of Coins for Fruits Python/Java solution

Both Python and Java implementations typically follow the same DP recurrence. Python often uses collections.deque for the monotonic queue, while Java implementations use ArrayDeque. The optimized solution runs in O(n) time and O(n) space.

Q: How to solve Minimum Number of Coins for Fruits in O(n)?

Formulate the problem as dp[i] = prices[i] + min(dp[j]) for j in the reachable range after buying fruit i. Process indices from right to left and maintain the minimum dp value in that range using a monotonic deque. Each index enters and leaves the deque once, giving O(n) total time.

Q: What is the best approach for Minimum Number of Coins for Fruits?

The optimal approach uses dynamic programming with a monotonic queue. Define dp[i] as the minimum cost starting from fruit i and transition to the minimum dp value in the reachable range. Using a deque to maintain a sliding window minimum reduces the complexity to O(n) time and O(n) space.

Q: Is Minimum Number of Coins for Fruits asked at Google/Amazon/Meta?

Dynamic programming problems involving range transitions and sliding minimum structures are common in interviews at companies like Google, Amazon, and Meta. Variants that combine DP with heaps or monotonic queues frequently appear in algorithm rounds.

Q: What data structure is used in Minimum Number of Coins for Fruits?

The main data structures are a priority queue (min-heap) for the greedy approach and a deque for the monotonic queue optimization. The dynamic programming solution also uses an array to store minimum costs for each starting index.

Q: What is the time complexity of Minimum Number of Coins for Fruits?

The optimized dynamic programming solution runs in O(n) time using a monotonic queue to maintain the minimum transition value. A heap-based greedy alternative runs in O(n log n) time due to priority queue operations.

MediumArray Dynamic Programming Queue Heap (Priority Queue)31 min read

Practice this problem

Problem Statement

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

The fruit market has the following reward for each fruit:

If you purchase the i^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] 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⁵

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.

Approach 1: Greedy Approach

The Greedy Approach involves starting from the most expensive fruit and moving downwards. By purchasing the costly fruits which have the potential to give maximum savings by allowing multiple subsequent fruits for free, we minimize the total number of coins required for purchasing all fruits. Prioritize buying fruits that eliminate the need to buy several subsequent fruits.

The function minCoins calculates the minimum coins required to buy all the fruits. It iterates from the end of the prices array towards the start, accumulating the cost and effectively skipping the number of steps based on the index being processed.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the number of fruits.
Space Complexity: O(1), as it uses only constant space.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

The Dynamic Programming Approach constructs a solution where at each step, it calculates the minimum cost of purchasing all fruits up to that point. It uses a state array dp[i] representing the minimum cost to buy up to the i^th fruit. The idea is to leverage previously computed results for efficient calculation.

This DP approach in C uses an array `dp` to keep track of the minimum coins needed for different lengths of the fruits considered. By iterating and updating with the smallest costs, it ultimately provides the optimal result.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2), where n is the number of fruits.
Space Complexity: O(n).

Try this approach in the editor →

Approach 3: Memoization Search

We define a function dfs(i) to represent the minimum number of coins needed to buy all the fruits starting from the i-th fruit. The answer is dfs(1).

The execution logic of the function dfs(i) is as follows:

If i times 2 geq n, it means that buying the (i - 1)-th fruit is sufficient, and the remaining fruits can be obtained for free, so return prices[i - 1].
Otherwise, we can buy fruit i, and then choose a fruit j to start buying from the next i + 1 to 2i + 1 fruits. Thus, dfs(i) = prices[i - 1] + min_{i + 1 \le j \le 2i + 1} dfs(j).

To avoid redundant calculations, we use memoization to store the results that have already been computed. When encountering the same situation again, we directly return the result.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array prices.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Approach 4: Dynamic Programming

We can rewrite the memoization search in Solution 1 into a dynamic programming form.

Similar to Solution 1, we define f[i] to represent the minimum number of coins needed to buy all the fruits starting from the i-th fruit. The answer is f[1].

The state transition equation is f[i] = min_{i + 1 \le j \le 2i + 1} f[j] + prices[i - 1].

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array prices.

In the code implementation, we can directly use the prices array to store the f array, thus optimizing the space complexity to O(1).

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Approach 5: Dynamic Programming + Monotonic Queue Optimization

Observing the state transition equation in Solution 2, we can see that for each i, we need to find the minimum value of f[i + 1], f[i + 2], cdots, f[2i + 1]. As i decreases, the range of these values also decreases. This is essentially finding the minimum value in a sliding window with a narrowing range, which can be optimized using a monotonic queue.

We calculate from back to front, maintaining a monotonically increasing queue q, where the queue stores indices. If the front element of q is greater than i times 2 + 1, it means that the elements after i will not be used, so we dequeue the front element. If i is not greater than (n - 1) / 2, we can add prices[q[0] - 1] to prices[i - 1], and then add i to the back of the queue. If the fruit price corresponding to the back element of q is greater than or equal to prices[i - 1], we dequeue the back element until the fruit price corresponding to the back element is less than prices[i - 1] or the queue is empty, then add i to the back of the queue.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array prices.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(n), where n is the number of fruits. Space Complexity: O(1), as it uses only constant space.
Dynamic Programming Approach	Time Complexity: O(n^2), where n is the number of fruits. Space Complexity: O(n).
Memoization Search	—
Dynamic Programming	—
Dynamic Programming + Monotonic Queue Optimization	—

Detailed 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

Video Solution

2944. Minimum Number of Coins for Fruits • Ayush Rao • 1,923 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Number of Coins for Fruits easy or hard?

Minimum Number of Coins for Fruits is generally rated Medium difficulty. The base dynamic programming idea is straightforward, but recognizing the sliding window minimum optimization with a monotonic queue makes the problem more challenging.

Minimum Number of Coins for Fruits Python/Java solution

Both Python and Java implementations typically follow the same DP recurrence. Python often uses collections.deque for the monotonic queue, while Java implementations use ArrayDeque. The optimized solution runs in O(n) time and O(n) space.

How to solve Minimum Number of Coins for Fruits in O(n)?

Formulate the problem as dp[i] = prices[i] + min(dp[j]) for j in the reachable range after buying fruit i. Process indices from right to left and maintain the minimum dp value in that range using a monotonic deque. Each index enters and leaves the deque once, giving O(n) total time.

What is the best approach for Minimum Number of Coins for Fruits?

The optimal approach uses dynamic programming with a monotonic queue. Define dp[i] as the minimum cost starting from fruit i and transition to the minimum dp value in the reachable range. Using a deque to maintain a sliding window minimum reduces the complexity to O(n) time and O(n) space.

Is Minimum Number of Coins for Fruits asked at Google/Amazon/Meta?

Dynamic programming problems involving range transitions and sliding minimum structures are common in interviews at companies like Google, Amazon, and Meta. Variants that combine DP with heaps or monotonic queues frequently appear in algorithm rounds.

What data structure is used in Minimum Number of Coins for Fruits?

The main data structures are a priority queue (min-heap) for the greedy approach and a deque for the monotonic queue optimization. The dynamic programming solution also uses an array to store minimum costs for each starting index.

What is the time complexity of Minimum Number of Coins for Fruits?

The optimized dynamic programming solution runs in O(n) time using a monotonic queue to maintain the minimum transition value. A heap-based greedy alternative runs in O(n log n) time due to priority queue operations.

Ready to solve this problem?

Practice Minimum Number of Coins for Fruits with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance49.6%

Approaches5

Reading time31 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Greedy Approach

Code

Complexity

Approach 2: Dynamic Programming Approach

Code

Complexity

Approach 3: Memoization Search

Code

Approach 4: Dynamic Programming

Code

Approach 5: Dynamic Programming + Monotonic Queue Optimization

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents