1475. Final Prices With a Special Discount in a Shop

Problem Description

You are provided with an array called prices where each element prices[i] indicates the cost of the i-th item in a store. This store offers a special discount on each item. When you buy the i-th item, you get a discount equal to the value of prices[j], where j is the smallest index greater than i such that prices[j] is less than or equal to prices[i]. If there's no such item that fulfils the condition for the discount, then no discount is applied to the i-th item. The problem requires you to determine the actual price you would pay for each item after applying the special discount if applicable and return this as a new array of prices.

Intuition

The intuition behind the solution involves a stack to keep track of the items (by their indices) that we have not yet found a smaller price for. This is an optimization technique to make finding the next smaller price more efficient.

As we iterate over the array, we compare the current price with the price at the top of the stack:

If the current price is less than or equal to the price of the item at the top of the stack, it means we found a smaller price. Therefore, the item at the top of the stack is eligible for a discount equal to the current price. We then update the answer for the item at the top of the stack by subtracting the current price from it and pop this index from the stack.
If the current price is higher, it means this item could potentially offer a discount to the following items. So, we add the current index to the stack to signify that we have not yet found a smaller price for the item at this index.
We continue this process until we've looked at all the prices and the stack has ensured all items received their due discounts where applicable.

This approach leverages the property of monotonically decreasing stacks to optimize the process of finding the next smaller element, which makes it possible to solve the problem in linear time.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution utilizes a data structure called a stack to efficiently track indices of prices that are awaiting a discount. The stack property of "last-in, first-out" is particularly helpful here because it allows us to always consider the most recent item when looking for the next lower price.

Here is how the algorithm works:

We initialize an empty stack stk and a list ans that is a copy of the original prices list.
We iterate over each item in prices using its index i and value v. For each item, we check whether a discount can be applied based on the items in the stack.
Inside the loop, there's an inner while loop that checks if the stack is not empty and whether the price at the top of the stack (the last item that was put into the stack) is greater than or equal to the current price v.
- If this is true, it implies that the item corresponding to the index at the top of the stack is eligible for a discount of value v (the current item's price).
- We then pop the top index from the stack and subtract the discount v from the original price in the ans list at that index.
- This process continues until the stack is empty or the current price v is no longer less than or equal to the prices of items indexed in the stack.
After the inner while loop ends (meaning no more discounts can be applied or the stack is empty), the current index i is appended to the stack.
This implies that this item is now waiting to potentially give a discount to a future item, or it will not receive a discount itself if no cheaper item comes after it.
Once the iteration over all prices completes, the ans list will have been modified to contain the final prices after discount for each item.

By using the stack this way, each item is pushed and popped at most once, leading to a time complexity of O(n) where n is the number of items in prices, making the algorithm efficient and suitable for larger datasets.

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 using a small example:

Imagine we have the following prices: [4, 2, 3, 7, 5]. We want to calculate the final price for each item after applying the special discount according to our problem description and solution approach.

We initialize an empty stack stk and a list ans that is a copy of the original prices list, thus ans would initially be [4, 2, 3, 7, 5].

Start at index 0 with price 4. Stack is currently empty, so push 0. Stack: [0]
Move to index 1 with price 2. The top of the stack refers to price 4. Since 2 is smaller than 4, apply discount to ans[0]: ans[0] = 4 - 2. Pop 0 from the stack and push 1 on the stack. Stack: [1], ans becomes [2, 2, 3, 7, 5].
Proceed to index 2 with price 3. The top index 1 has the price 2, which is not greater than 3, so no discount is applied. Push 2 onto the stack. Stack: [1, 2]
Next is index 3 with price 7. 2 (from ans[2]) is smaller than 7, so no discount is applied to the price at index 3. Push 3 onto the stack. Stack: [1, 2, 3]
Lastly, index 4 with price 5. Compare with top of the stack index 3 which is 7. Since 5 is lower, apply discount to ans[3]: ans[3] = 7 - 5. Pop 3 from the stack. Next, compare with top of the stack index 2, which has the price 3. Price 3 is not higher than 5, so we stop and push 4 onto the stack. Stack: [1, 2, 4], ans becomes [2, 2, 3, 2, 5].

Finally, there are no more items to consider, and the ans array holds the final discounted prices. The function would return the ans array, which is [2, 2, 3, 2, 5]. This is how much you would pay for each item after applying the discounts.

Solution Implementation

1from typing import List
2
3class Solution:
4    def finalPrices(self, prices: List[int]) -> List[int]:
5        # Initialise a stack to keep track of the indices of prices
6        stack = []
7      
8        # Make a copy of the prices list to store the final prices after discounts
9        final_prices = prices[:]
10      
11        # Iterate over the prices with their corresponding indices
12        for index, value in enumerate(prices):
13            # Check for prices in the stack that are greater or equal to the current price
14            while stack and prices[stack[-1]] >= value:
15                # Apply the discount to the price at the top of the stack by subtracting
16                # the current value from it, then pop it from the stack
17                final_prices[stack.pop()] -= value
18          
19            # Push the current index onto the stack
20            stack.append(index)
21      
22        # Return the modified prices list with applied discounts
23        return final_prices
24

1class Solution {
2    public int[] finalPrices(int[] prices) {
3        // Create a stack to keep track of the indices of prices that haven't found a discount yet
4        Deque<Integer> stack = new ArrayDeque<>();
5        int n = prices.length;
6        // Initialize an array to hold the final prices after applying the discounts
7        int[] finalPrices = new int[n];
8
9        // Iterate over the array of prices
10        for (int i = 0; i < n; ++i) {
11            // Store the original price as the final price for now
12            finalPrices[i] = prices[i];
13
14            // Check if the current price can be a discount for the price at the top of the stack
15            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
16                // Apply discount to the top price and update it in the finalPrices array
17                finalPrices[stack.pop()] -= prices[i];
18            }
19
20            // Push the current index onto the stack
21            stack.push(i);
22        }
23
24        // Return the array of final prices after applying the discounts where applicable
25        return finalPrices;
26    }
27}
28

1class Solution {
2public:
3    vector<int> finalPrices(vector<int>& prices) {
4        // Create a stack to keep track of indices of prices
5        stack<int> indexStack;
6      
7        // Initialize the answer vector with the original prices
8        vector<int> discountedPrices = prices;
9      
10        // Loop through each price
11        for (int i = 0; i < prices.size(); ++i) {
12            // While stack is not empty and the current price is less than or equal to
13            // the price at the top of the stack (indicates a discount is available)
14            while (!indexStack.empty() && prices[indexStack.top()] >= prices[i]) {
15                // Apply the discount to the price at the top index
16                discountedPrices[indexStack.top()] -= prices[i];
17                // Pop the index from the stack as the discount has been applied
18                indexStack.pop();
19            }
20            // Push the current index onto the stack
21            indexStack.push(i);
22        }
23      
24        // Return the vector containing final prices after discounts
25        return discountedPrices;
26    }
27};
28

1function finalPrices(prices: number[]): number[] {
2    // Initialize the length of the prices array to avoid recomputation.
3    const lengthOfPrices = prices.length;
4
5    // Initialize the result array to store the final discounted prices.
6    const discountedPrices = new Array(lengthOfPrices);
7
8    // Initialize a stack to keep track of prices from the end to start.
9    const priceStack: number[] = [];
10
11    // Iterate over the prices array from the end to the beginning.
12    for (let i = lengthOfPrices - 1; i >= 0; i--) {
13        // Store the current price for readability.
14        const currentPrice = prices[i];
15
16        // Check prices in the stack; if any price is greater than the current price,
17        // it cannot be a discount for the current price, so remove it.
18        while (priceStack.length !== 0 && priceStack[priceStack.length - 1] > currentPrice) {
19            priceStack.pop();
20        }
21
22        // Calculate the discounted price for the current item.
23        // If the stack is empty, no discount is applied (hence the nullish coalescing operator ?? is used).
24        discountedPrices[i] = currentPrice - (priceStack[priceStack.length - 1] ?? 0);
25
26        // Add the current price to the stack for possible future discounts.
27        priceStack.push(currentPrice);
28    }
29
30    // Return the array of discounted prices.
31    return discountedPrices;
32}
33

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of elements in the prices list. This is because each element is pushed onto the stack at most once, and each element is popped from the stack at most once. The while loop will only iterate for each element if there is a matching discount, so even though there's a nested loop, it does not result in a quadratic time complexity.

The space complexity of the code is also O(n). This is due to the stack stk that, in the worst case, can hold all the elements from the prices list if no discounts apply. Additionally, the ans list is a copy of the prices list and thus also takes O(n) space.

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