2969. Minimum Number of Coins for Fruits II
Problem Description
Imagine you're in a market packed with various exotic fruits where each type has a different price. The array prices
provided to you represents the cost of each fruit at the respective index, with the index starting from 1.
Here's the twist: whenever you buy fruit i
at the cost of prices[i]
, you are entitled to take the next i
fruits free of charge. However, you also have the option to pay for any of these fruits you're entitled to for free so you can receive the same offer again with the fruit you just paid for.
Your goal is to strategize your purchases to minimize the total amount you spend to obtain every single fruit available.
Intuition
First, we need to understand the straightforward but inefficient approach. We could start from the first fruit and calculate the minimum cost for every possible range of fruits we can get for free, which would be a dynamic programming solution with a state equation. But this basic DP solution has an complexity, given that we would have multiple overlapping calculations as we choose different starting points. This complexity is not feasible for large n
.
To optimize, we observe that there's a pattern of finding the minimum value in a decreasing range of upcoming free fruits. This pattern is akin to having a sliding window that narrows as we move backwards through the array. A monotonic queue, keeping track of minimum values in a dynamically changing range, would help us efficiently manage these updates.
The trick lies in filling this monotonic queue correctly. As we go backwards from the last fruits, we maintain a window that represents the minimum prices we might pay if we start our offer from a given point. If the head of the queue points to a fruit that's out of range for our current i
, it's removed from consideration. Also, we keep the queue in increasing order so that the head always holds the index of the fruit with the minimal possible cost.
Furthermore, if we are at a position where we can still take offers, i.e., not past the half of the list, we increment the price at our current location with the minimal price found so far, since this is the additional cost we incur when choosing to buy this fruit and not taking it for free. Then, we ensure our queue's tail only holds relevant, cost-efficient options by popping out the more expensive ones. Once we have our queue ready, we move to the next i
and repeat the process until we reach the beginning of the array. The first element will now have the minimum cost for the whole set of fruits.
Learn more about Queue, Dynamic Programming, Monotonic Queue and Heap (Priority Queue) patterns.
Solution Approach
The provided solution employs a monotonic queue data structure to leverage the optimization potential identified in the problem's structure. A monotonic queue is essentially a deque that maintains elements in a sorted order so that you can efficiently get the minimum (or maximum) of the elements currently in the queue.
Let's step through the implementation of the solution:
-
We initialize a double-ended queue,
q
, which will be used to represent our monotonic queue. -
We start iterating through the prices array from the end towards the beginning (in reverse). This is done using a loop that goes from
n
down to1
. -
Inside the loop, we check whether the current head of the queue (
q[0]
) points to a fruit index that is out of our current "offer" range (i * 2 + 1
). If so, wepopleft
from the queue since these fruits are no longer relevant to the current context. -
Assuming we have not crossed half of the list
(i <= (n - 1) // 2)
, we need to consider the cost of starting an offer from the current fruit. Therefore, we add to the current fruit's price (prices[i - 1]
) the price associated with the best starting point for the next offer (prices[q[0] - 1]
). -
Before adding the current index
i
to the queue, we need to make sure it fits the monotonic property of the queue. To do this, we compare the price at the current index with the prices at the indices currently in the queue. Specifically, we look at the tail of the queue and pop off any elements whose associated prices are greater than or equal to the price at the current index. -
After ensuring that the queue remains monotonic, we
append
the current indexi
to the queue.
This iterative process loop ensures that at each step we maintain a queue which points to indices of the starting points for offers that give us the lowest subsequent prices. By the end of the loop, the prices[0]
will hold the minimum cost needed to purchase all the fruits according to the given offers, since it will have been updated with the minimal costs from all the stages of the process.
The time complexity of this solution is significantly better than the naive dynamic programming solution since we only manipulate each element a constant number of times due to the queue operations, resulting in an overall complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following prices
array for the fruits in the market: [6, 2, 3, 4, 5, 1]
. Remember, the index starts from 1.
-
We begin by initializing our double-ended queue,
q
. It is empty at the start. -
We start iterating from the end of the
prices
array backward. On our first iteration,i = 6
, we directly append this index toq
because it's the first element we're processing. -
Then we go to
i = 5
. Sincei <= (n - 1) // 2
doesn't hold (5 is not less than or equal to 2), we don't adjust the price of the 5th fruit (prices[4]
). We check the queue's tail and sinceprices[i - 1]
is less thanprices[q[-1] - 1]
(1 is less than 6), we popq[-1]
and then appendi
toq
. -
Continue to
i = 4
. Now,i <= (n - 1) // 2
is true (4 is less than or equal to 2). We updateprices[3]
to beprices[3] + prices[q[0] - 1]
, which changes the fourth fruit's cost to4 + 1 = 5
. The 4th index is then appended toq
because it has a lower cost (prices[3]
) compared to the last element inq
. -
At
i = 3
,i
is still less than or equal to half the size, so we updateprices[2]
with the cost ofprices[q[0] - 1]
.prices[2]
becomes3 + 5 = 8
. We will pop the end ofq
sinceprices[2]
is not less thanprices[3]
, then appendi
. -
For
i = 2
, updateprices[1]
to2 + 8 = 10
. Now, we compareprices[1]
to the last element price inq
and find thatprices[1]
is greater. Therefore, we do not make any changes toq
. -
Finally, at
i = 1
, we add the minimum price fromq
which is 8, makingprices[0]
equal to6 + 8 = 14
.
This will be our prices
array at the end: [14, 10, 8, 5, 1, 6]
. The minimum cost to get all the fruits by applying the offer strategy is stored at the first index, which is 14
. The double-ended queue (q
) ensures we always add the smallest subsequent cost possible as we work backwards.
This step-by-step method shows how the monotonic queue aids in maintaining a sorted order of potential costs without having to sort the entire array at each iteration, lending to the solution's time complexity.
Solution Implementation
1from collections import deque
2from typing import List
3
4class Solution:
5 def minimumCoins(self, prices: List[int]) -> int:
6 # Determine the number of elements in the prices list
7 num_prices = len(prices)
8 queue = deque() # Initialize a double-ended queue to manage indices
9
10 # Iterate backwards through the list of prices
11 for i in range(num_prices, 0, -1):
12
13 # Remove indices from the front of the queue that are no longer needed
14 while queue and queue[0] > i * 2 + 1:
15 queue.popleft()
16
17 # If we are in the first half of the prices list (or exact middle when odd),
18 # increment the current price by the price at the front of the queue
19 if i <= (num_prices - 1) // 2:
20 prices[i - 1] += prices[queue[0] - 1]
21
22 # Remove indices from the end of the queue while their corresponding prices
23 # are greater than or equal to the current price
24 while queue and prices[queue[-1] - 1] >= prices[i - 1]:
25 queue.pop()
26
27 # Append the current index to the queue
28 queue.append(i)
29
30 # Return the modified first element of prices list which now contains the result
31 return prices[0]
32
1class Solution {
2 public int minimumCoins(int[] prices) {
3 // The length of the prices array
4 int numPrices = prices.length;
5
6 // Create a double-ended queue to store indices
7 Deque<Integer> deque = new ArrayDeque<>();
8
9 // Iterate from the last index to the first
10 for (int i = numPrices; i > 0; --i) {
11 // Remove indexes from the front of the queue that are out of the current range
12 while (!deque.isEmpty() && deque.peek() > i * 2 + 1) {
13 deque.poll();
14 }
15
16 // If the current index is in the first half of the array, update the price at that index
17 if (i <= (numPrices - 1) / 2) {
18 prices[i - 1] += prices[deque.peek() - 1];
19 }
20
21 // Remove indexes from the back of the queue that have a price higher or equal to the current price
22 while (!deque.isEmpty() && prices[deque.peekLast() - 1] >= prices[i - 1]) {
23 deque.pollLast();
24 }
25
26 // Add the current index to the end of the queue
27 deque.offer(i);
28 }
29
30 // The price at the first index after all operations is the answer
31 return prices[0];
32 }
33}
34
1#include <vector>
2#include <deque>
3using namespace std;
4
5class Solution {
6public:
7 // Function to compute the minimum number of coins to buy all items.
8 // Prices is a vector of prices of items the shopkeeper has in ascending order of quality.
9 int minimumCoins(vector<int>& prices) {
10 int itemCount = prices.size(); // Total number of items.
11 deque<int> indicesQueue; // Deque to store relevant indices for price comparison.
12
13 // Run a loop from the end to the beginning of the prices vector.
14 for (int currentIndex = itemCount; currentIndex > 0; --currentIndex) {
15 // Remove indices from the front of the deque which are not relevant anymore.
16 while (!indicesQueue.empty() && indicesQueue.front() > currentIndex * 2 + 1) {
17 indicesQueue.pop_front();
18 }
19
20 // If the item is in the first half (or less) of the list,
21 // add to its price the price of the item at the current front of the deque (which is the minimum).
22 if (currentIndex <= (itemCount - 1) / 2) {
23 prices[currentIndex - 1] += prices[indicesQueue.front() - 1];
24 }
25
26 // Remove indices from the back which have a price greater than or equal to the current price.
27 // As we're looking for the minimum price, these are no longer useful.
28 while (!indicesQueue.empty() && prices[indicesQueue.back() - 1] >= prices[currentIndex - 1]) {
29 indicesQueue.pop_back();
30 }
31
32 // Add the current index to the deque. It may serve as the minimum for a future item.
33 indicesQueue.push_back(currentIndex);
34 }
35
36 // The minimum price to buy all items would be found at prices[0] after the loop ends.
37 return prices[0];
38 }
39};
40
1// Node interface to represent a node in the deque
2interface Node<T> {
3 value: T;
4 next: Node<T> | null;
5 prev: Node<T> | null;
6}
7
8// Global variables to simulate a Deque
9let front: Node<any> | null = null;
10let back: Node<any> | null = null;
11let size: number = 0;
12
13// Function to check if the deque is empty
14function isEmpty(): boolean {
15 return size === 0;
16}
17
18// Function to get the size of the deque
19function getSize(): number {
20 return size;
21}
22
23// Function to get the front value of the deque
24function frontValue(): any | undefined {
25 return front?.value;
26}
27
28// Function to get the back value of the deque
29function backValue(): any | undefined {
30 return back?.value;
31}
32
33// Function to insert an element at the front of the deque
34function pushFront<T>(val: T): void {
35 const newNode: Node<T> = { value: val, next: front, prev: null };
36 if (isEmpty()) {
37 front = newNode;
38 back = newNode;
39 } else {
40 front!.prev = newNode;
41 front = newNode;
42 }
43 size++;
44}
45
46// Function to insert an element at the back of the deque
47function pushBack<T>(val: T): void {
48 const newNode: Node<T> = { value: val, next: null, prev: back };
49 if (isEmpty()) {
50 front = newNode;
51 back = newNode;
52 } else {
53 back!.next = newNode;
54 back = newNode;
55 }
56 size++;
57}
58
59// Function to remove an element from the front of the deque
60function popFront<T>(): T | undefined {
61 if (isEmpty()) {
62 return undefined;
63 }
64 const value = front!.value;
65 front = front!.next;
66 if (front) {
67 front.prev = null;
68 } else {
69 back = null;
70 }
71 size--;
72 return value;
73}
74
75// Function to remove an element from the back of the deque
76function popBack<T>(): T | undefined {
77 if (isEmpty()) {
78 return undefined;
79 }
80 const value = back!.value;
81 back = back!.prev;
82 if (back) {
83 back.next = null;
84 } else {
85 front = null;
86 }
87 size--;
88 return value;
89}
90
91// Function to find the minimum number of coins required
92function minimumCoins(prices: number[]): number {
93 const n = prices.length;
94 for (let i = n; i; --i) {
95 while (getSize() && frontValue()! > i * 2 + 1) {
96 popFront();
97 }
98 if (i <= (n - 1) >> 1) {
99 prices[i - 1] += prices[frontValue()! - 1];
100 }
101 while (getSize() && prices[backValue()! - 1] >= prices[i - 1]) {
102 popBack();
103 }
104 pushBack(i);
105 }
106 return prices[0];
107}
108
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
. Here's a walkthrough of how we come up with this analysis:
- Iterating through the range of
n
happens inO(n)
time. - For each
i
in the range, the while loops run. However, each element is added and removed from the dequeq
at most once during the entire loop. Thus, each element's operations are constant-time operations because deque operations such aspopleft
andpop
areO(1)
. - The rest of the operations inside the for loop are constant time, so they don't affect the overall linear
O(n)
complexity.
Space Complexity
The space complexity of the code is O(n)
as well, and here is why:
- A deque
q
is used which in the worst case may contain all elements if they are in strictly decreasing order. That means it could hold up ton
elements, thus takingO(n)
space. - There are no other data structures that hold a number of elements proportional to
n
. Therefore, the deque is the main contributor to the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
Want a Structured Path to Master System Design Too? Donāt Miss This!