Problem of The Day: Final Prices With a Special Discount in a Shop

Problem Statement

problem

Brute force [accepted]

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

Editorial

Approach 2: Monotonic Stack

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # Create a copy of prices array to store discounted prices
        result = prices.copy()

        stack = deque()

        for i in range(len(prices)):
            # Process items that can be discounted by current price
            while stack and prices[stack[-1]] >= prices[i]:
                # Apply discount to previous item using current price
                result[stack.pop()] -= prices[i]
            # Add current index to stack
            stack.append(i)

        return result