Loading problems...
TL;DR: Use a Monotonic Stack to find the "Next Smaller Element" for each item in the array in linear time, subtracting that value from the original price.
The problem asks us to process an array of item prices. For each item at index i, we need to look ahead to subsequent indices j > i to find the first price that is less than or equal to prices[i]. If such a price exists, it acts as a discount, and we subtract it from the original price. If no such price exists to the right, the item is sold at its original price.
This is a classic variation of the "Next Greater Element" problem, specifically adapted for LeetCode 1475 as a "Next Smaller or Equal Element" search.
The naive approach involves simulating the problem statement directly using nested loops. For every item in the array, we scan all subsequent items to find the first valid discount.
prices array to store the results.i from to .0n-1i, start an inner loop j from i+1 to n-1.prices[j] <= prices[i].prices[j] from the result at i and break the inner loop (since we only apply the first valid discount).python# Pseudo-code for Brute Force n = length(prices) answer = copy(prices) for i from 0 to n-1: for j from i+1 to n-1: if prices[j] <= prices[i]: answer[i] = prices[i] - prices[j] break return answer
Complexity Analysis:
[1, 2, 3, 4, 5]), for every element i, the inner loop runs until the end of the array without finding a discount.Why it fails: While the constraints for Final Prices With a Special Discount in a Shop are small (), allowing an solution to pass, this approach fails to demonstrate the optimal algorithmic thinking required for technical interviews. If the input size were increased to (common in similar problems), this solution would result in a Time Limit Exceeded (TLE).
The key intuition is to process the prices while keeping track of items that are "waiting" for a discount.
As we iterate through the prices array from left to right, we encounter prices that might serve as discounts for previous items. Specifically, if we are at index j, prices[j] can be the discount for a previous index i if prices[j] <= prices[i].
We can maintain a stack of indices. This stack will satisfy a specific invariant: the prices corresponding to the indices in the stack will always be in strictly increasing order.
Why strictly increasing?
Visual Description: Imagine walking through the array. You hold onto indices of items you want to buy. When you see a new price, you check your list of held indices. If the new price is lower than the price of an item you are holding, you immediately apply the discount to that held item and stop holding it (pop it). You continue this until the new price is no longer lower than your held items, then you add the current item's index to your hand.

Let's trace the algorithm with prices = [8, 4, 6, 2, 3].
answer = [8, 4, 6, 2, 3], stack = [].0. Stack: [0].0 (Price 8). Is 4 <= 8? Yes.answer[0] = 8 - 4 = 4.1. Stack: [1].1 (Price 4). Is 6 <= 4? No.2. Stack: [1, 2]. (Note: Prices at indices [1, 2] are [4, 6], which is increasing).2 (Price 6). Is 2 <= 6? Yes.answer[2] = 6 - 2 = 4.1 (Price 4). Is 2 <= 4? Yes.answer[1] = 4 - 2 = 2.3. Stack: [3].3 (Price 2). Is 3 <= 2? No.4. Stack: [3, 4].answer = [4, 2, 4, 2, 3].The algorithm is correct because it strictly adheres to the definition of the problem using the LIFO (Last-In-First-Out) property of the stack.
k such that we have not yet found a j > k with prices[j] <= prices[k].i currently being processed, it is to the right of all indices currently in the stack.prices[i] <= prices[stack.top()] is met, we guarantee that prices[i] is the first valid discount found for stack.top(). Once popped, an index is never processed again, ensuring we don't overwrite the correct discount with a later, further one.cppclass Solution { public: vector<int> finalPrices(vector<int>& prices) { vector<int> answer = prices; stack<int> st; // Monotonic stack storing indices for (int i = 0; i < prices.size(); ++i) { // While stack is not empty and current price is a valid discount // for the item at the top of the stack while (!st.empty() && prices[i] <= prices[st.top()]) { int idx = st.top(); st.pop(); // Apply discount answer[idx] = prices[idx] - prices[i]; } st.push(i); } return answer; } };
javaclass Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] answer = prices.clone(); // Copy original prices Deque<Integer> stack = new ArrayDeque<>(); // Use Deque as stack for indices for (int i = 0; i < n; i++) { // While stack is not empty and current price is <= price at stack top while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) { int idx = stack.pop(); // Apply discount: original price - current price answer[idx] = prices[idx] - prices[i]; } stack.push(i); } return answer; } }
pythonclass Solution: def finalPrices(self, prices: List[int]) -> List[int]: answer = prices[:] # Create a copy of prices stack = [] # Stack to store indices for i, price in enumerate(prices): # While stack is not empty and we found a discount while stack and price <= prices[stack[-1]]: idx = stack.pop() answer[idx] = prices[idx] - price stack.append(i) return answer
Time Complexity:
prices array once.Space Complexity:
The Monotonic Stack pattern used in Final Prices With a Special Discount in a Shop is highly transferable. It is the optimal strategy for any problem requiring the "Next Greater" or "Next Smaller" element.
Q: Why do I get the wrong answer when I store values in the stack instead of indices?
prices[i] in the stack instead of i.answer array to update.Q: Why are some items in my output 0 or incorrect?
answer array with zeros and only updating it when a discount is found.answer as a copy of .pricesQ: Why does my loop terminate early or run infinitely?
while loop (e.g., prices[i] < prices[stack.top()] instead of <=).prices[j] <= prices[i]. If the prices are equal, it counts as a discount.