Final Prices With a Special Discount in a Shop — Solution
Final Prices With a Special Discount in a Shop solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Final Prices With a Special Discount in a Shop is an easy coding problem on arrays, stack and monotonic stack, asked in Amazon, Adobe and Dream11 interviews.
- Difficulty: Easy
- Topics: Arrays, Stack, Monotonic Stack
- Asked at: Amazon, Adobe, Dream11
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array prices where prices[i] is the price of the i-th item.
Buying item i earns a discount equal to prices[j], where j is the smallest index greater than i with prices[j] <= prices[i]. If no such j exists, there is no discount.
Return the array of prices actually paid.
Example 1
Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Example 2
Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: No item has a cheaper item after it.
Example 3
Input: prices = [10,1,1,6]
Output: [9,0,1,6]
Constraints
1 <= prices.length <= 401 <= prices[i] <= 1000
Hints for Final Prices With a Special Discount in a Shop
Hint 1
This is the classic "next smaller or equal element" problem.
Hint 2
Keep a stack of indices whose discount is still unknown, with prices increasing from bottom to top.
Hint 3
When a new price arrives, it discounts every index on the stack whose price is at least as large.
How to solve Final Prices With a Special Discount in a Shop
Next smaller-or-equal element with a monotonic stack: indices waiting for a discount sit on the stack with increasing prices; a new price pays off every index whose price is at least as large.
Approach
- For each
i, while the stack top's price>= prices[i], popjand setout[j] = prices[j] - prices[i]. - Push
i.
Why it works
The first later index with a price ≤ the current one is by definition the first that pops it; indices never popped keep their full price.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Use
>=, not>— an equal price counts as a discount.
Reference solution
Python
def finalPrices(prices):
out = list(prices)
stack = []
for i, price in enumerate(prices):
while stack and prices[stack[-1]] >= price:
j = stack.pop()
out[j] = prices[j] - price
stack.append(i)
return outJava
public static int[] finalPrices(int[] prices) {
int[] out = prices.clone();
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
int j = stack.pop();
out[j] = prices[j] - prices[i];
}
stack.push(i);
}
return out;
}C++
vector<int> finalPrices(vector<int>& prices) {
vector<int> out = prices;
vector<int> stack;
for (int i = 0; i < (int) prices.size(); i++) {
while (!stack.empty() && prices[stack.back()] >= prices[i]) {
int j = stack.back();
stack.pop_back();
out[j] = prices[j] - prices[i];
}
stack.push_back(i);
}
return out;
}JavaScript
var finalPrices = function(prices) {
const out = prices.slice();
const stack = [];
for (let i = 0; i < prices.length; i++) {
while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[i]) {
const j = stack.pop();
out[j] = prices[j] - prices[i];
}
stack.push(i);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure