What is the brute force approach and complexity for Final Prices With a Special Discount in a Shop?

For each item, walk right until the first price ≤ it with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Final Prices With a Special Discount in a Shop?

Keep unpaid items on a stack; a new price ≤ top pays off and pops them with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Final Prices With a Special Discount in a Shop?

Look for key signals in the prompt: "the first index j after i" indicates "First to the right" → a next-element question, not min/max of a range.; "prices[j] <= prices[i]" indicates We want something smaller (or equal) → the stack keeps the bigger ones waiting, so it is increasing.; "otherwise no discount" indicates Items left on the stack at the end get a default (here: full price)..

Final Prices With a Special Discount in a Shop

Easy·LeetCode #1475Basic Anchor

LeetCode

Jump:

30-Second Mental ModelMonotonic Stack — next smaller (or equal) element, increasing stack

Complexity:O(N²)→O(N)

Key Insight

Read the prices left to right. Keep a stack of indices whose discount has not been found yet. When price prices[i] arrives, every waiting item on top with a price >= prices[i] has just found its first cheaper-or-equal item: subtract prices[i] from it and pop it. Then push i, because it now waits for its own discount.

Core Validity Invariant

Prices on the stack strictly increase from bottom to top. Anything ≤ a waiting item below it would already have paid that item off and popped it.

Problem

A shop sells items in a row. prices[i] is the price of item i.

The shop has a special deal: when you buy item i, you get a discount equal to prices[j], where j is the first index after i with prices[j] <= prices[i]. If there is no such item, you get no discount.

Return an array where entry i is the price you actually pay for item i.

Input

An integer array prices.

Output

An array answer of the same length, where answer[i] is prices[i] minus its discount.

Example 1

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

Output: [4, 2, 4, 2, 3]

8 gets 4 off (4 is the first price ≤ 8 to its right). 4 gets 2 off. 6 gets 2 off. 2 gets nothing (no price ≤ 2 after it). 3 is last, so no discount.

Example 2

Input: prices = [1, 2, 3, 4, 5]

Output: [1, 2, 3, 4, 5]

Prices only go up, so no item ever finds a cheaper-or-equal one after it.

Example 3

Input: prices = [10, 1, 1, 6]

Output: [9, 0, 1, 6]

10 gets 1 off. The first 1 gets 1 off from the second 1, because equal counts. The second 1 and 6 get nothing.

Constraints

• 1 ≤ prices.length ≤ 500
• 1 ≤ prices[i] ≤ 1000

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
For one item, which item to its right gives the discount? The cheapest one, or the first good one?
2.
Does a price that is exactly equal count?
3.
If item 5 is waiting for a discount and item 7 comes along that is ≤ it, does item 5 still need to look further?
4.
While you read left to right, which items are still "waiting" for their discount?
5.
If a new price is small enough to pay off one waiting item, which waiting items does it pay off first?

Brute force approach

Idea

Do exactly what the problem says. For every item i, look at i + 1, i + 2, … and stop at the first price that is <= prices[i]. Subtract it. If you reach the end, the item keeps its full price.

Thinking process

1
The discount for item i depends only on the items after it.
2
"First" means we stop as soon as we find one. No need to look at all of them.
3
So a nested loop: outer loop picks i, inner loop walks j right and breaks on the first prices[j] <= prices[i].
4
In the worst case (prices going up, so nobody finds a discount) every inner loop runs to the end: O(n²).

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> ans = prices;
        for (int i = 0; i < n; i++) {
            // Walk right and stop at the FIRST price that is <= prices[i].
            for (int j = i + 1; j < n; j++) {
                if (prices[j] <= prices[i]) {
                    ans[i] = prices[i] - prices[j];
                    break;   // only the first one counts
                }
            }
            // No such j: no discount, ans[i] stays prices[i].
        }
        return ans;
    }
};

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = prices.clone();
        for (int i = 0; i < n; i++) {
            // Walk right and stop at the FIRST price that is <= prices[i].
            for (int j = i + 1; j < n; j++) {
                if (prices[j] <= prices[i]) {
                    ans[i] = prices[i] - prices[j];
                    break;   // only the first one counts
                }
            }
            // No such j: no discount, ans[i] stays prices[i].
        }
        return ans;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        ans = prices[:]
        for i in range(n):
            # Walk right and stop at the FIRST price that is <= prices[i].
            for j in range(i + 1, n):
                if prices[j] <= prices[i]:
                    ans[i] = prices[i] - prices[j]
                    break   # only the first one counts
            # No such j: no discount, ans[i] stays prices[i].
        return ans

export function finalPrices(prices: number[]): number[] {
    const n = prices.length;
    const ans = [...prices];
    for (let i = 0; i < n; i++) {
        // Walk right and stop at the FIRST price that is <= prices[i].
        for (let j = i + 1; j < n; j++) {
            if (prices[j] <= prices[i]) {
                ans[i] = prices[i] - prices[j];
                break;   // only the first one counts
            }
        }
        // No such j: no discount, ans[i] stays prices[i].
    }
    return ans;
}

Complexity

Time O(N²)Space O(1)

Extra space is O(1) apart from the answer array. With n ≤ 500 this is fast enough on LeetCode, but the same idea at n = 10^5 would be 10^10 steps. The stack version is the one to learn.

Optimized approach

Idea

Start from brute force

For every item, brute force walks right one step at a time until it finds a price ≤ its own.

Find the repeated work

Different items walk over the same stretch of prices again and again. In [1, 2, 3, 4, 5], item 0 checks 4 prices, item 1 checks 3 of the same prices, and so on. Each walk throws away what it learned.

Define the state — what variables do I need?

st: vector<int> used as a stack of indices that have not found their discount yet. Their prices increase from bottom to top.
ans: Starts as a copy of prices. ans[j] -= prices[i] when i turns out to be j's discount.
i: The price being read now. It may be the discount for some waiting items.

Define validity

Prices on the stack strictly increase from bottom to top. Anything ≤ a waiting item below it would already have paid that item off and popped it.

Define the transitions — when does each pointer move, and why is it safe?

stack not empty and prices[top] >= prices[i]

ans[top] -= prices[i]; pop

top was still waiting, so no item between it and i was ≤ it. So i is its first cheaper-or-equal item. It is settled forever.

stack empty or prices[top] < prices[i]

stop popping; push i

The top is cheaper than prices[i], so i is no discount for it. Everything below the top is even cheaper, so they are safe too. i joins the waiting list on top, keeping the stack increasing.

after the loop

leave the remaining indices alone

No price ≤ them ever came. ans already holds their full price.

What does the current window add to the answer?

Each pop settles one item's final price. Items never popped pay full price. Together that is the whole answer array.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> ans = prices;   // default: no discount
        vector<int> st;             // indices still waiting for a discount; prices increase bottom -> top

        for (int i = 0; i < n; i++) {
            // prices[i] is the first price <= every waiting price that is >= it.
            while (!st.empty() && prices[st.back()] >= prices[i]) {
                ans[st.back()] -= prices[i];
                st.pop_back();   // this item got its discount; it is done
            }
            st.push_back(i);     // now prices[i] waits for its own discount
        }
        // Whatever is left on the stack never found a smaller-or-equal price: full price.
        return ans;
    }
};

import java.util.*;

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = prices.clone();   // default: no discount
        Deque<Integer> st = new ArrayDeque<>(); // indices still waiting for a discount; prices increase bottom -> top

        for (int i = 0; i < n; i++) {
            // prices[i] is the first price <= every waiting price that is >= it.
            while (!st.isEmpty() && prices[st.peek()] >= prices[i]) {
                ans[st.pop()] -= prices[i];   // this item got its discount; it is done
            }
            st.push(i);     // now prices[i] waits for its own discount
        }
        // Whatever is left on the stack never found a smaller-or-equal price: full price.
        return ans;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        ans = prices[:]   # default: no discount
        st: List[int] = []   # indices still waiting for a discount; prices increase bottom -> top

        for i in range(n):
            # prices[i] is the first price <= every waiting price that is >= it.
            while st and prices[st[-1]] >= prices[i]:
                ans[st.pop()] -= prices[i]   # this item got its discount; it is done
            st.append(i)     # now prices[i] waits for its own discount

        # Whatever is left on the stack never found a smaller-or-equal price: full price.
        return ans

export function finalPrices(prices: number[]): number[] {
    const n = prices.length;
    const ans = [...prices];   // default: no discount
    const st: number[] = [];   // indices still waiting for a discount; prices increase bottom -> top

    for (let i = 0; i < n; i++) {
        // prices[i] is the first price <= every waiting price that is >= it.
        while (st.length > 0 && prices[st[st.length - 1]] >= prices[i]) {
            ans[st.pop()!] -= prices[i];   // this item got its discount; it is done
        }
        st.push(i);     // now prices[i] waits for its own discount
    }
    // Whatever is left on the stack never found a smaller-or-equal price: full price.
    return ans;
}

Complexity

Time O(N)Space O(N)

The inner while can pop many items for one price, but each index is popped at most once in total, so all the pops together are at most n.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each item, walk right until the first price ≤ it	O(N²)	O(1)
Optimal	Keep unpaid items on a stack; a new price ≤ top pays off and pops them	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“the first index j after i”"First to the right" → a next-element question, not min/max of a range.
“prices[j] <= prices[i]”We want something smaller (or equal) → the stack keeps the bigger ones waiting, so it is increasing.
“otherwise no discount”Items left on the stack at the end get a default (here: full price).

For each element+first one to the right+smaller or equal→Monotonic Stack — next smaller (or equal) element, increasing stack

This is the anchor for next smaller. It is the mirror of next greater: there the stack is decreasing and a bigger arrival pops; here the stack is increasing and a smaller-or-equal arrival pops. The only twist in this problem is the =: an equal price counts, so we pop on >=, not >. The next question (GFG Next Smaller Element) uses strictly smaller and shows the right-to-left way of building the same answer.

Don't make this mistake

Using strict < (equal prices ignored)

✗ while (!st.empty() && prices[st.back()] > prices[i])

✓ while (!st.empty() && prices[st.back()] >= prices[i])

The problem says "less than or equal". With >, [10, 1, 1, 6] gives the first 1 no discount and returns [9, 1, 1, 6] instead of [9, 0, 1, 6].

Using a decreasing stack (that finds next greater)

✗ while (!st.empty() && prices[st.back()] < prices[i]) { ... } // pops when a BIGGER price comes

✓ while (!st.empty() && prices[st.back()] >= prices[i]) { ... } // pops when a smaller-or-equal price comes

Pattern-confusion trap: the next-greater template pops when a bigger value arrives, so the stack decreases. Copying it here gives each item the first more expensive item, which is the wrong discount. Ask: "what kind of arrival settles a waiting item?" Here it is a cheaper one, so the stack must increase.

Taking the cheapest price to the right

✗ ans[i] = prices[i] - *min_element(prices.begin() + i + 1, prices.end());

The discount is the first price ≤ mine, not the smallest. In [8, 4, 6, 2, 3], item 8 gets 4 off, not 2.

Pushing prices instead of indices

✗ st.push_back(prices[i]); // later: which ans[] do I update?

✓ st.push_back(i); // ans[st.back()] -= prices[i]

When we pop, we must write into that item's slot in ans. With only the price on the stack you do not know where it came from (and prices can repeat).

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Next Smaller Element