< Back





1475. Final Prices With a Special Discount in a Shop

Classic monotonically increasing stack problem, and we can recognize this after breaking down the
problem statement. The problem statement asks us to find the final prices of items in a shop given a
special discount. This special discount is as follows:

  For some item, i, in prices[i], if some item j, where j > i, satisifies prices[j] <= prices[i],
  you only pay prices[i] less prices[j].

Basically, if we buy an item and an item of lesser value, we get a discount on the more expensive
item. A monotonically increasing stack allows us to apply the discount when we discover an item
of lesser value than the item currently at the top of the stack. The monotonic stack also retains
the order of the items we encounter in the original array.

The solution is as follows:


  class Solution:
      def finalPrices(self, prices: List[int]) -> List[int]:
          stack = []

          for i in range(len(prices)):
              while stack and prices[i] <= prices[stack[-1]]:
                  prices[stack.pop()] -= prices[i]

              stack.append(i)

          return prices


_ Time Complexity:

  O(n) - We inspect all prices in the input array.

_ Space Complexity:

  O(n) - We maintain a monotonically increasing stack.