Final Prices With a Special Discount in a Shop
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 a "next smaller or equal element" problem. For each position i, we scan to the right looking for the first j > i where prices[j] <= prices[i]. That framing connects it to the monotonic stack pattern, but a direct scan is enough to get a working solution.
Key Constraints:
1 <= prices.length <= 500→ With n at most 500, an O(n^2) brute force does at most about 125,000 comparisons, well within time limits. There is no pressure to optimize.1 <= prices[i] <= 1000→ All prices are positive, so every final price stays non-negative and there are no edge cases around zero or negative inputs.
Approach 1: Brute Force
Intuition
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 translates the problem statement directly into code. For each index i, scan from i + 1 onward. The first j where prices[j] <= prices[i] gives the discount. If no such j exists, the item keeps its original price.
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.
The brute force rescans the same elements repeatedly. The next approach removes that rescanning with a stack that tracks items still waiting for a discount.
Approach 2: Monotonic Stack
Intuition
The "next smaller or equal element" pattern has a standard O(n) solution using a monotonic stack. Instead of asking "for item i, where is its discount?" we invert it: "when we reach a cheaper item, which earlier items does it discount?"
Iterate left to right. Maintain a stack of indices whose discounts are not yet resolved. When we reach a new price prices[j], compare it to the price at the top of the stack. If prices[j] <= prices[stack.top()], then j is the discount index for that stack item, so we pop it and apply the discount. We keep popping while the condition holds, since a single cheap item can be the discount for several earlier items.
The stack stays in increasing order of prices from bottom to top, because we only push an index after popping everything greater than or equal to the current price. At any moment the stack holds indices whose prices form an increasing sequence, all still waiting for a discount.
An index i stays on the stack until some later price qualifies as its discount. Since we scan left to right, the moment we pop i is the first j > i with prices[j] <= prices[i], the minimum such index the problem asks for. No earlier qualifying price gets skipped: any price between i and j that was less than or equal to prices[i] would have popped i before the scan reached j.
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): - While the stack is not empty and
prices[j] <= prices[stack.top()], pop the top indexifrom the stack and setresult[i] = prices[i] - prices[j]. - Push
jonto 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).