Clearance Discounts
EasyStack
Problem
A shelf of items is priced prices[0..n-1] from left to right. During a clearance sale, each item is discounted by the price of the first item to its right whose price is less than or equal to its own. If no such item exists, the item keeps its full price.
Return the final price of every item.
Example 1
- Input:
- prices = [9, 4, 6, 2, 3]
- Output:
- [5, 2, 4, 2, 3]
9 is discounted by 4, 4 by 2, 6 by 2; 2 and 3 have no cheaper-or-equal item to their right.
Example 2
- Input:
- prices = [1, 2, 3]
- Output:
- [1, 2, 3]
Constraints
- 1 ≤ prices.length ≤ 10^5
- 1 ≤ prices[i] ≤ 10^4
Hint
Show the first hint
For each item you need the next item to the right with price ≤ it: a 'next smaller-or-equal element' question.
Walkthrough
How to approach it
01Clarify before coding
- Does an equal price count as a discount? Yes, less than or equal.
- Only the first such item to the right? Yes, the nearest one.
- Can I modify the input? Return a new array to be safe.
02Brute force
For each item scan to the right until the first price ≤ it.
Cost: O(n²) for increasing prices: 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.