[Leetcode problems]1475. Final Prices With a Special Discount in a Shop

Given the 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 array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.

Examples:
Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3]
Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5]

This question first appeared in the Leetcode Biweekly Contest 28, and the brute force approach is straightforward enough to come up with. However, inspired by @lee215, it could be also solved with the monotone stack, which amazingly reduces O(n^2) to O(n).

Brute force approach – O(n^2)

It uses a nested for-loop to check that, for each item, whether there is a coming number that is smaller or equal to it.

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

Monotone stack – O(n)

A monotone stack refers to a stack structure where numbers in it are increasing only or decreasing only. With a monotone stack, given a number, we can find the first item that is smaller or larger than it. More importantly, it achieves O(n) time complexity.

Here we implements an increasing monotone stack, and when we find one smaller item (than the last item in the stack), we would pop all larger items before pushing it into the stack.

def finalPrices(self, prices: List[int]) -> List[int]:
    stack = []
    for i,val in enumerate(prices):
        while stack and prices[stack[-1]] >= val:
            prices[stack.pop()] -= val
        stack.append(i)
    return prices

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments