EasyArrayStackMonotonic StackUpdated Sep 2026

1475. Final Prices With a Special Discount in a Shop

Asked at Uber

Difficulty

Easy

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an array prices, where prices[i] is the price of the i-th item in a shop.

For each item i, look to its right for the first item j (with j > i) whose price is less than or equal to prices[i]. If such an item exists, you get a discount equal to prices[j], so the final price is prices[i] - prices[j]. If no such item exists to the right, there is no discount and you pay the full price.

Return an array answer where answer[i] is the final price of item i after applying its discount.

Find the first smaller-or-equal price to the right

prices8462301234Item 0 has price 8; the first later price <= 8 is 4 atindex 1, so the discount is 4.prices8462301234Item 2 has price 6; the first later price <= 6 is 2 atindex 3, so the discount is 2.answer4242301234Items 3 and 4 have no smaller-or-equal price to theirright, so they keep their full prices.
For each item, the discount is the first price to its right that is less than or equal to it.

Constraints

  • ●1 <= prices.length <= 500
  • ●1 <= prices[i] <= 1000

Examples

Example 1
Inputprices = [8,4,6,2,3]
Output[4,2,4,2,3]
WhyItem 0 (8) finds 4 at index 1, so it pays 8-4=4. Item 1 (4) finds 2 at index 3, so it pays 4-2=2. Item 2 (6) also finds 2 at index 3, so it pays 6-2=4. Items 3 and 4 have nothing smaller-or-equal to their right, so they keep their full prices 2 and 3.
Example 2
Inputprices = [1,2,3,4,5]
Output[1,2,3,4,5]
WhyThe prices only grow as you move right, so no item ever finds a later price that is less than or equal to it. Every item pays full price.
Example 3
Inputprices = [10,1,1,6]
Output[9,0,1,6]
WhyItem 0 (10) finds 1 at index 1, so it pays 10-1=9. Item 1 (1) finds an equal 1 at index 2, so it pays 1-1=0. Item 2 (1) has nothing smaller-or-equal to its right, so it pays 1. Item 3 (6) also has nothing to its right, so it pays 6.

Asked At

1 companies
CompanyDifficulty
UberEasyView all Uber questions →

How to Think About It

1

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).

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.

3

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.

4

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.

5

After processing all elements, remaining stack elements have no discount (no smaller or equal element to the right).

6

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.

Monotonic stack of waiting indices

stack (indices)0← topStart: push index 0 (price 8). It waits for a laterprice <= 8.stack (indices)12← topPrice 4 at index 1 pops index 0 (discount 8-4=4), thenindex 1 is pushed; price 6 at index 2 is larger, so itis pushed too.stack (indices)34← topPrice 2 at index 3 pops index 2 (6-2=4) and index 1(4-2=2), then index 3 is pushed; price 3 at index 4 islarger, so it is pushed.while stack and prices[i] <= prices[top]: result[pop()] -= prices[i]push i
The stack holds indices still waiting for a discount; a new price pops all waiting indices it can discount.
ComplexityTime O(n)Space O(n)Each index is pushed onto the stack once and popped at most once, so the total work is linear; the stack can hold up to n indices.

What Trips People Up in Real Interviews

1

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].

2

Using a monotonic decreasing stack instead of increasing. For "next smaller or equal", you want an increasing stack.

3

Forgetting that the condition is prices[j] <= prices[i] (less than OR EQUAL), not just strictly less than.

4

Not handling the case where no smaller element exists to the right. Those items keep their original price.

5

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

O(n) time
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 result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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)`.