2969. Minimum Number of Coins for Fruits II

HardQueueArrayDynamic ProgrammingMonotonic QueueHeap (Priority Queue)

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 $O(n^2)$ 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 to 1.
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, we popleft 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 index i 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 $O(n^2)$ dynamic programming solution since we only manipulate each element a constant number of times due to the queue operations, resulting in an overall $O(n)$ complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example 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 to q because it's the first element we're processing.
Then we go to i = 5. Since i <= (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 since prices[i - 1] is less than prices[q[-1] - 1] (1 is less than 6), we pop q[-1] and then append i to q.
Continue to i = 4. Now, i <= (n - 1) // 2 is true (4 is less than or equal to 2). We update prices[3] to be prices[3] + prices[q[0] - 1], which changes the fourth fruit's cost to 4 + 1 = 5. The 4th index is then appended to q because it has a lower cost (prices[3]) compared to the last element in q.
At i = 3, i is still less than or equal to half the size, so we update prices[2] with the cost of prices[q[0] - 1]. prices[2] becomes 3 + 5 = 8. We will pop the end of q since prices[2] is not less than prices[3], then append i.
For i = 2, update prices[1] to 2 + 8 = 10. Now, we compare prices[1] to the last element price in q and find that prices[1] is greater. Therefore, we do not make any changes to q.
Finally, at i = 1, we add the minimum price from q which is 8, making prices[0] equal to 6 + 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 $O(n)$ 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 in O(n) time.
For each i in the range, the while loops run. However, each element is added and removed from the deque q at most once during the entire loop. Thus, each element's operations are constant-time operations because deque operations such as popleft and pop are O(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 to n elements, thus taking O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know