Final Prices With a Special Discount in a Shop
Last Updated: March 29, 2026
Understanding the Problem
For each item in the array, we need to find the first item to its right whose price is less than or equal to the current item's price. If such an item exists, we subtract its price from the current item's price. If not, the price stays the same.
This is essentially a "next smaller or equal element" problem. For each position i, we're scanning to the right looking for the first j > i where prices[j] <= prices[i]. Once we frame it this way, the connection to the monotonic stack pattern becomes clear. But let's start simple.
Key Constraints:
1 <= prices.length <= 500→ With n at most 500, even an O(n^2) brute force performs at most 250,000 operations. That's well within time limits, so brute force is perfectly fine here.1 <= prices[i] <= 1000→ All prices are positive integers. No need to worry about negatives or zeros in the input.
Approach 1: Brute Force
Intuition
The most direct approach: for each item, look at every item after it and find the first one whose price is less than or equal to the current item's price. Subtract that price to get the discount.
This is exactly what the problem description says to do. For each index i, start a scan from i + 1 onward. The first j where prices[j] <= prices[i] gives us the discount. If no such j exists, the item keeps its original price.
With n up to 500, this nested loop runs at most 125,000 iterations. That's fast enough, so there's nothing wrong with this approach for the given constraints.
Algorithm
- Create a result array as a copy of
prices. - For each index
ifrom 0 to n - 1, iterate through indicesjfromi + 1to n - 1. - If
prices[j] <= prices[i], subtractprices[j]fromresult[i]and break out of the inner loop. - Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n items, we potentially scan all items to its right. In the worst case (a strictly increasing array), every item scans to the end, giving n(n-1)/2 comparisons.
- Space Complexity: O(n). We create a result array of size n.
This approach works but does redundant scanning. What if we could resolve multiple items at once using a stack that tracks unresolved discounts?
Approach 2: Monotonic Stack
Intuition
The brute force works fine for n = 500, but this problem is a textbook case of the "next smaller or equal element" pattern, which the monotonic stack solves elegantly in O(n).
Here's the key idea. Instead of asking "for item i, where's the discount?" we flip the question: "when we encounter a cheap item, which previous items does it discount?"
We iterate left to right through the array. We maintain a stack of indices whose discounts we haven't resolved yet. When we reach a new price prices[j], we check: is this price less than or equal to the price at the top of the stack? If so, j is the discount index for that stack item. We pop it and apply the discount. We keep popping as long as the condition holds, because this new price could be the discount for multiple previous items.
The stack naturally stays in increasing order of prices from bottom to top. We only push an index onto the stack after popping everything that's greater than or equal to the current price. So at any moment, the stack holds indices whose prices form an increasing sequence, and they're all still "waiting" for their discount.
The stack maintains a list of indices whose "next smaller or equal" element hasn't been found yet. When we encounter a price that's small enough to act as a discount, we resolve all pending items on the stack that it qualifies for. Because we process left to right and the stack keeps items in increasing price order, the first qualifying price we encounter for each item is guaranteed to be the nearest one to its right.
Each index gets pushed onto the stack exactly once and popped at most once. So across all iterations, the total number of push and pop operations is at most 2n, giving us O(n) total work.
Algorithm
- Create a result array as a copy of
prices. - Initialize an empty stack (it will hold indices).
- Iterate through the array from left to right (index
jfrom 0 to n - 1):
a. While the stack is not empty and prices[j] <= prices[stack.top()], pop the top index i from the stack and set result[i] = prices[i] - prices[j].
b. Push j onto the stack.
- Items remaining in the stack have no discount, so their prices stay unchanged (already correct from the initial copy).
- Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n). Each element is pushed onto the stack once and popped at most once, giving 2n operations total. The amortized cost per element is O(1).
- Space Complexity: O(n). The stack can hold at most n indices (when the array is strictly increasing). The result array also uses O(n).