Final Prices With a Special Discount in a Shop
Asked at Uber
Problem
Given prices where prices[i] is the price of the ith item, for each item apply a discount equal to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Return the final prices after all discounts.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Easy | View all Uber questions → |
How to Think About It
Brute force: for each item i, scan forward to find the first item j > i with prices[j] <= prices[i]. Time is O(n^2).
Use a monotonic increasing stack to find the next smaller or equal element for each position. This is the classic "next smaller element" problem.
Iterate from left to right. For each price, while the stack is not empty and the current price is <= the price at the stack top, pop from the stack and apply the discount.
The stack stores indices. When you encounter a price that is <= the price at the stack top, the current price is the discount for the top element.
After processing all elements, remaining stack elements have no discount (no smaller or equal element to the right).
Example: prices = [8,4,6,2,3]. Stack processing: push 0 (price 8). At i=1 (price 4), 4 <= 8, so pop 0, discount prices[0] by 4 -> prices[0]=4. Push 1. At i=2 (price 6), 6 > 4, push 2. At i=3 (price 2), 2 <= 6 so pop 2, discount prices[2] by 2 -> prices[2]=4. 2 <= 4 so pop 1, discount prices[1] by 2 -> prices[1]=2. Push 3. At i=4 (price 3), 3 > 2, push 4. Result: [4,2,4,2,3].
Optimal Approach
Step 1: Initialize a stack to store indices and a result array that starts as a copy of prices.
Step 2: Iterate through prices with index i from 0 to n-1.
Step 3: While the stack is not empty and prices[i] <= prices[stack.top()], pop the index from the stack and subtract prices[i] from result[popped_index].
Step 4: Push i onto the stack.
Step 5: After the loop, return the result array.
Step 6: Example walkthrough with prices = [10,1,1,6]:
i=0: stack empty, push 0. stack=[0].
i=1: prices[1]=1 <= prices[0]=10. Pop 0, result[0]=10-1=9. Push 1. stack=[1].
i=2: prices[2]=1 <= prices[1]=1. Pop 1, result[1]=1-1=0. Push 2. stack=[2].
i=3: prices[3]=6 > prices[2]=1. Push 3. stack=[2,3].
Result: [9,0,1,6].
Time: O(n) since each element is pushed and popped at most once. Space: O(n) for the stack.
What Trips People Up in Real Interviews
Confusing the discount direction. The discount is prices[j] (the smaller price), not prices[i] - prices[j]. The final price is prices[i] - prices[j].
Using a monotonic decreasing stack instead of increasing. For "next smaller or equal", you want an increasing stack.
Forgetting that the condition is prices[j] <= prices[i] (less than OR EQUAL), not just strictly less than.
Not handling the case where no smaller element exists to the right. Those items keep their original price.
Trying to solve with a nested loop and claiming it is O(n) because of some pruning. The monotonic stack gives true O(n).
Solution Code
class Solution:
def finalPrices(self, prices: list[int]) -> list[int]:
result = prices[:]
stack = []
for i in range(len(prices)):
while stack and prices[i] <= prices[stack[-1]]:
idx = stack.pop()
result[idx] -= prices[i]
stack.append(i)
return resultFrequently Asked Questions
What is the Final Prices With a Special Discount in a Shop problem?
Given prices where prices[i] is the price of the ith item, for each item apply a discount equal to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Return the final prices after all discounts.
How do you solve Final Prices With a Special Discount in a Shop?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Final Prices With a Special Discount in a Shop?
Final Prices With a Special Discount in a Shop is asked at Uber. It is a easy difficulty problem.
What are common mistakes on Final Prices With a Special Discount in a Shop?
- Confusing the discount direction. The discount is prices[j] (the smaller price), not prices[i] - prices[j]. The final price is prices[i] - prices[j].
- Using a monotonic decreasing stack instead of increasing. For "next smaller or equal", you want an increasing stack.
- Forgetting that the condition is `prices[j] <= prices[i]` (less than OR EQUAL), not just strictly less than.
- Not handling the case where no smaller element exists to the right. Those items keep their original price.
- Trying to solve with a nested loop and claiming it is `O(n)` because of some pruning. The monotonic stack gives true `O(n)`.