Final Prices With a Special Discount: Monotonic Stack Basics

LeetCode gives you a pricing array and asks a simple question: for each item, can you find a discount? 1475. Final Prices With a Special Discount in a Shop is rated easy, but it is one of the best entry points into monotonic stacks. The brute force is obvious, and the optimal solution shows you exactly why a stack helps.

The problem

You are given an array prices where prices[i] is the price of the i-th item. For each item i, find the first item j where j > i and prices[j] <= prices[i]. The final price you pay is prices[i] - prices[j]. If no such j exists, you pay the full price.

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

Item 0 costs 8. The first later item with a price <= 8 is item 1 (price 4), so you pay 8 - 4 = 4. Item 1 costs 4, and the first later item with a price <= 4 is item 3 (price 2), so you pay 4 - 2 = 2. Items 3 and 4 have no qualifying discount after them, so you pay their full prices.

Why this problem matters

This is a "next smaller or equal element" problem in disguise. For each index, you need the first value to the right that is less than or equal to the current value. That pattern appears constantly in stack-based problems: daily temperatures (next greater), largest rectangle in histogram (next smaller), stock span (previous greater). Final Prices is the gentlest version of this family. Once you see how a stack eliminates redundant scanning here, you can apply the same idea to every next-element variant.

The key insight

The brute force scans forward from each index looking for a discount. That throws away work because you re-examine the same elements over and over. A monotonic stack remembers the "candidates" for future discounts, and when you process a new item, you instantly know which candidates it resolves. Each element enters and leaves the stack at most once, so the total work is O(n).

You can iterate right to left, maintaining a stack of prices you have seen so far. For each item, pop anything from the stack that is strictly greater than the current price (those values cannot be a discount for anything further left). Then, if the stack is not empty, the top is your discount. Push the current price and move on.

The solution

Brute force (O(n^2)):

def final_prices_brute(prices):
    n = len(prices)
    result = prices[:]

    for i in range(n):
        for j in range(i + 1, n):
            if prices[j] <= prices[i]:
                result[i] = prices[i] - prices[j]
                break

    return result

For each item, scan right until you find a qualifying discount. This works but does redundant work when the array is large or mostly decreasing.

Monotonic stack (O(n)):

def final_prices(prices):
    n = len(prices)
    result = prices[:]
    stack = []

    for i in range(n - 1, -1, -1):
        while stack and stack[-1] > prices[i]:
            stack.pop()

        if stack:
            result[i] = prices[i] - stack[-1]

        stack.append(prices[i])

    return result

Walk right to left. The stack holds prices in non-decreasing order from top to bottom. For each item, pop anything on top that is strictly greater (it cannot serve as a discount for the current item or anything further left). If the stack still has elements, the top is the discount. Then push the current price.

Visual walkthrough

Let's trace through prices = [8, 4, 6, 2, 3] from right to left. Each step shows the current index, the stack state, and the result array being filled in.

Notice a few things. The stack always stays in non-decreasing order from top to bottom. Each price gets pushed once and popped at most once, which is what keeps the total work at O(n). In step 4, price 6 gets popped because it is greater than 4, and the stack reveals price 2 as the correct discount.

Complexity analysis

Time for the stack solution is O(n). Each of the n elements is pushed onto the stack exactly once and popped at most once. The while loop can pop multiple elements in a single iteration of the for loop, but across the entire algorithm the total number of pops is at most n.

Space is O(n) in the worst case. If the prices array is strictly increasing (like [1, 2, 3, 4, 5]), nothing gets popped during the right-to-left pass, and the stack holds all n elements. In practice, the stack is usually much smaller.

The building blocks

1. The monotonic stack pop loop

The core pattern that drives the solution:

while stack and stack[-1] > prices[i]:
    stack.pop()

This maintains a stack where the top element is always <= prices[i]. You are removing candidates that can never serve as a discount for the current item or any item further to the left. The same loop appears in Daily Temperatures (pop when the current temp is greater), Largest Rectangle (pop when the current height is smaller), and dozens of other problems. The only thing that changes is the comparison operator and what you compute on each pop.

2. Peek-then-push

After the pop loop, the answer for the current index comes from peeking at the stack top:

if stack:
    result[i] = prices[i] - stack[-1]
stack.append(prices[i])

This is the "use the stack to answer a query, then add yourself as a future candidate" pattern. It works because the pop loop has already removed everything that is irrelevant. Whatever remains on top is the first qualifying element to the right.

3. Right-to-left iteration for next-element queries

for i in range(n - 1, -1, -1):
    # process prices[i]

When you need the "next element to the right" with some property, iterating right to left and building up a stack of candidates is a clean approach. You process each element exactly when you need to answer its query, and the stack already contains all the future elements you have seen. This direction pairs naturally with "next smaller," "next smaller or equal," and similar queries.

Edge cases

• All prices equal, like [5, 5, 5, 5]: every item (except the last) gets a full discount from the next item. Result is [0, 0, 0, 5].
• Strictly increasing like [1, 2, 3, 4]: no item has a later item with a smaller or equal price. Result is the original array unchanged.
• Strictly decreasing like [4, 3, 2, 1]: every item gets a discount from the very next item. Result is [1, 1, 1, 1].
• Single element [10]: no discount possible. Result is [10].
• Two elements [5, 3]: result is [2, 3]. [3, 5]: result is [3, 5] (5 is not <= 3).

From understanding to recall

You have seen how a monotonic stack turns an O(n^2) scan into an O(n) single-pass algorithm for Final Prices. The logic is short: a pop loop, a peek, and a push. But the details matter under pressure. Do you pop on > or >=? Do you store prices or indices? Do you iterate left to right or right to left?

These are not conceptual gaps. They are recall gaps. Spaced repetition closes them. You practice writing the pop loop from scratch at increasing intervals until the pattern is automatic. When a "next smaller element" variant appears in an interview, you do not hesitate. You just write it.

Related posts

• Daily Temperatures - The classic monotonic stack problem for finding the next greater element, using the same pop-when-resolved pattern
• Largest Rectangle in Histogram - A harder monotonic stack problem where you compute areas on each pop instead of discounts
• Next Greater Element I - Another easy monotonic stack problem that pairs a stack with a hash map for cross-array lookups

CodeBricks breaks Final Prices into its monotonic stack building blocks and drills them independently with spaced repetition. You type the pop loop, the peek-then-push, and the right-to-left iteration from scratch until each piece is in your long-term memory. When any next-element variant shows up, the code flows without hesitation.