Final Prices With a Special Discount in a Shop

Difficulty: Easy | Acceptance: 84.10% | Paid: No Topics: Array, Stack, Monotonic Stack

You are given an integer array prices where prices[i] is the price of the ith item in a shop.

There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop considering the special discount.

• Examples
• Constraints
• Brute Force
• Monotonic Stack

Examples

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
- Item 0 (price 8) has a discount equivalent to item 1 (price 4), so final price is 8 - 4 = 4.
- Item 1 (price 4) has a discount equivalent to item 3 (price 2), so final price is 4 - 2 = 2.
- Item 2 (price 6) has a discount equivalent to item 3 (price 2), so final price is 6 - 2 = 4.
- Items 3 and 4 have no discount, so final price is 2 and 3 respectively.

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: No item has a discount, so the final prices remain the same.

Input: prices = [10,1,1,6]
Output: [9,0,1,6]
Explanation: 
- Item 0 (price 10) has a discount equivalent to item 1 (price 1), so final price is 10 - 1 = 9.
- Item 1 (price 1) has a discount equivalent to item 2 (price 1), so final price is 1 - 1 = 0.
- Item 2 (price 1) has no discount, so final price is 1.
- Item 3 (price 6) has no discount, so final price is 6.

Constraints

- 1 <= prices.length <= 500
- 1 <= prices[i] <= 1000

Brute Force

Intuition For each element in the array, we can simply scan all the elements to its right to find the first element that is less than or equal to it.

Steps

• Create a result array and copy the prices into it.
• Iterate through the array with index i.
• For each i, iterate through indices j from i + 1 to the end of the array.
• If prices[j] <= prices[i], update result[i] to be prices[i] - prices[j] and break the inner loop.
• Return the result array.

from typing import List

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        res = prices[:]
        for i in range(n):
            for j in range(i + 1, n):
                if prices[j] <= prices[i]:
                    res[i] = prices[i] - prices[j]
                    break
        return res

Complexity

• Time: O(n²) - In the worst case, for every element, we traverse the rest of the array.
• Space: O(1) - We only use a constant amount of extra space (excluding the output array).
• Notes: Simple to implement but inefficient for large input sizes.

Monotonic Stack

Intuition We can optimize the search for the next smaller or equal element using a monotonic stack. By iterating from right to left, we maintain a stack of potential discount values. The top of the stack will always be the nearest smaller element to the right of the current element.

Steps

• Initialize an empty stack and a result array.
• Iterate through the prices array from right to left.
• While the stack is not empty and the top element of the stack is greater than the current price, pop from the stack. This ensures we maintain a monotonic increasing stack.
• If the stack is not empty, the top element is the discount for the current price. Calculate prices[i] - stack.top(). If the stack is empty, there is no discount.
• Push the current price onto the stack.
• Return the result array.

from typing import List

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        res = prices[:]
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and stack[-1] > prices[i]:
                stack.pop()
            if stack:
                res[i] = prices[i] - stack[-1]
            stack.append(prices[i])
        return res

Complexity

• Time: O(n) - Each element is pushed and popped from the stack at most once.
• Space: O(n) - In the worst case, the stack may store all elements.
• Notes: This is the optimal solution for finding the next smaller element.