Problem Description

You have an array prices where each element represents the price of an item in a shop. The shop offers a special discount system:

• When you buy the i-th item, you get a discount equal to prices[j]
• Here, j is the smallest index where:
  • j > i (the item must come after your current item)
  • prices[j] <= prices[i] (its price must be less than or equal to your current item's price)
• If no such item exists, you get no discount

Your task is to return an array where each element represents the final price you pay for that item after applying the discount.

Example walkthrough: If prices = [8, 4, 6, 2, 3]:

• Item at index 0 (price 8): Next item ≤ 8 is at index 1 (price 4), so final price = 8 - 4 = 4
• Item at index 1 (price 4): Next item ≤ 4 is at index 3 (price 2), so final price = 4 - 2 = 2
• Item at index 2 (price 6): Next item ≤ 6 is at index 3 (price 2), so final price = 6 - 2 = 4
• Item at index 3 (price 2): No item after it is ≤ 2, so final price = 2
• Item at index 4 (price 3): No items after it, so final price = 3

The solution uses a monotonic stack approach, traversing the array from right to left. The stack maintains elements in increasing order from bottom to top. For each element:

1. Pop all elements from the stack that are greater than the current element (they can't be discounts)
2. If the stack has elements, the top element is the discount
3. Push the current element onto the stack for future items to consider

This efficiently finds the first smaller or equal element to the right of each position in O(n) time.

Intuition

The key insight is recognizing this as a "next smaller element" problem. For each item, we need to find the first item to its right that has a price less than or equal to it.

Why does a monotonic stack work here? Let's think about it step by step:

1. Processing from right to left: If we traverse from the end of the array backwards, by the time we reach position i, we've already seen all elements that come after it. This allows us to know what discounts are available for the current item.

2. Why maintain an increasing stack?: Consider this scenario - if we have prices [5, 3, 7] and we're at position 0 (price 5), we need to find the next element ≤ 5. The element 3 qualifies, but what about 7? Since 7 > 5, it will never be a valid discount for price 5. But more importantly, if 3 exists before 7, then 7 will never be chosen as a discount for any element to the left of position 0 either, because 3 will always be encountered first and 3 < 7.

3. The stack invariant: By maintaining elements in increasing order (from bottom to top), we ensure that:

   • The smallest valid discount is always at the top of the stack
   • Any element that can't possibly be a discount (because a smaller element exists before it) is removed

4. The popping logic: When we encounter a new price x, we pop all elements greater than x from the stack. Why? Because x is now a better discount option for any future items - it's both smaller and appears earlier (remember we're going backwards).

This approach elegantly handles the constraint that we need the first element to the right that satisfies our condition, not just any element. The monotonic property ensures we always have the optimal discount available at the top of the stack.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution uses a monotonic stack to efficiently find the next smaller or equal element for each position. Here's how the implementation works:

Algorithm Steps:

1. Initialize an empty stack stk that will maintain prices in increasing order from bottom to top.

2. Traverse the array in reverse using for i in reversed(range(len(prices))):

   • We go backwards so that when processing position i, we've already seen all elements that come after it.

3. For each position i:

   • Store the current price in variable x = prices[i]

4. Maintain the monotonic property with while stk and x < stk[-1]:

   • Pop all elements from the stack that are strictly greater than x
   • These elements can never be discounts for future items because x is smaller and appears earlier

5. Apply the discount with if stk: prices[i] -= stk[-1]:

   • If the stack is not empty after popping, the top element stk[-1] is the first element to the right that is ≤ x
   • Subtract this discount from the original price

6. Add current element to stack with stk.append(x):

   • This element might be a discount for items to its left

7. Return the modified array which now contains the final prices after discounts.

Time Complexity: O(n) - Each element is pushed and popped from the stack at most once.

Space Complexity: O(n) - In the worst case (prices in increasing order), the stack contains all elements.

Example Walkthrough with prices = [8, 4, 6, 2, 3]:

• i=4: x=3, stack empty → no discount, stack = [3]
• i=3: x=2, pop 3 (2 < 3) → no discount, stack = [2]
• i=2: x=6, keep 2 → discount = 2, prices[2] = 6-2 = 4, stack = [2, 6]
• i=1: x=4, pop 6, keep 2 → discount = 2, prices[1] = 4-2 = 2, stack = [2, 4]
• i=0: x=8, keep all → discount = 4, prices[0] = 8-4 = 4, stack = [2, 4, 8]

Final result: [4, 2, 4, 2, 3]

Example Walkthrough

Let's walk through a small example with prices = [10, 6, 8, 5] to understand how the monotonic stack solution works.

Initial Setup:

• Start with an empty stack
• Process array from right to left (indices 3 → 2 → 1 → 0)

Step 1: Process index 3 (price = 5)

• Current price x = 5
• Stack is empty, so no elements to pop
• No discount available (stack empty)
• Final price remains 5
• Push 5 onto stack: stack = [5]

Step 2: Process index 2 (price = 8)

• Current price x = 8
• Check stack top: 5 ≤ 8, so don't pop
• Discount available: top of stack = 5
• Final price = 8 - 5 = 3
• Push 8 onto stack: stack = [5, 8]

Step 3: Process index 1 (price = 6)

• Current price x = 6
• Stack top is 8, and 6 < 8, so pop 8
• New stack: [5]
• Check again: 5 ≤ 6, so don't pop
• Discount available: top of stack = 5
• Final price = 6 - 5 = 1
• Push 6 onto stack: stack = [5, 6]

Step 4: Process index 0 (price = 10)

• Current price x = 10
• Stack top is 6, and 10 ≥ 6, so don't pop
• Discount available: top of stack = 6
• Final price = 10 - 6 = 4
• Push 10 onto stack: stack = [5, 6, 10]

Result: [4, 1, 3, 5]

Verification:

• Index 0 (10): Next element ≤ 10 is 6 at index 1 → 10 - 6 = 4 ✓
• Index 1 (6): Next element ≤ 6 is 5 at index 3 → 6 - 5 = 1 ✓
• Index 2 (8): Next element ≤ 8 is 5 at index 3 → 8 - 5 = 3 ✓
• Index 3 (5): No elements after it → stays 5 ✓

The stack maintains increasing order, ensuring we always find the first (nearest) element to the right that can serve as a discount.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array once in reverse order. Although there's a nested while loop inside the for loop, each element can be pushed onto and popped from the stack at most once throughout the entire execution. Therefore, the total number of operations across all iterations is at most 2n (each element is pushed once and popped at most once), resulting in an amortized time complexity of O(n), where n is the length of the array prices.

Space Complexity: O(n)

The algorithm uses a stack stk to store elements. In the worst case, when the prices are in strictly increasing order from right to left (or decreasing order in the original array), all elements would remain in the stack, requiring O(n) space. Therefore, the space complexity is O(n), where n is the length of the array prices.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using Wrong Comparison Operator

The Problem: A common mistake is using strict inequality (<) instead of less than or equal to (<=) when maintaining the monotonic stack:

# INCORRECT - This will miss valid discounts
while stack and current_price < stack[-1]:  # Wrong!
    stack.pop()

This error occurs because the problem states that the discount item must have prices[j] <= prices[i], meaning equal prices are valid discounts. Using strict inequality will incorrectly pop equal elements from the stack, causing them to be unavailable as discounts.

Example of the Bug: For prices = [10, 5, 5, 2]:

• Using <: Item at index 1 (price 5) would incorrectly get no discount (the next 5 would be popped)
• Correct output with <=: Item at index 1 gets discount of 5, resulting in price 0

The Solution: Use the correct comparison operator:

# CORRECT - Allows equal prices to serve as discounts
while stack and current_price <= stack[-1]:
    stack.pop()

Pitfall 2: Modifying Original Array Without Preserving Values

The Problem: The code modifies prices[i] in-place but then pushes the modified value to the stack:

# INCORRECT - Using modified price instead of original
if stack:
    prices[i] -= stack[-1]
stack.append(prices[i])  # Wrong! This appends the discounted price

This breaks the algorithm because future items need to compare against original prices, not discounted prices.

The Solution: Always preserve and use the original price for stack operations:

# CORRECT - Store original price before modification
current_price = prices[i]
while stack and current_price <= stack[-1]:
    stack.pop()
if stack:
    prices[i] -= stack[-1]
stack.append(current_price)  # Use original price

Pitfall 3: Traversing in Wrong Direction

The Problem: Attempting to solve this problem by traversing left to right:

# INCORRECT - Can't find future discounts when going forward
for i in range(len(prices)):
    # At position i, we haven't seen positions > i yet

When traversing left to right, we haven't seen the elements that come after the current position, making it impossible to determine the discount in a single pass.

The Solution: Always traverse from right to left so that when processing position i, all positions j > i have already been processed and are available in the stack:

# CORRECT - Process from right to left
for i in range(len(prices) - 1, -1, -1):
    # All elements to the right have been processed