Final Prices With a Special Discount in a Shop
Final Prices With a Special Discount in a Shop is a easy monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (monotonic stack), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan to the right) up.
Problem
A shop lists its items in a row with prices prices, where prices[i] is the price of item i. A special offer applies: when you buy item i, you get 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, item i gets no discount.
Return an array answer where answer[i] is the amount you actually pay for item i.
Examples
Example 1
- Input
prices = [10, 4, 7, 3, 9]- Output
[6, 1, 4, 3, 9]- Why
- 10 is discounted by 4, 4 by 3, 7 by 3; nothing cheaper or equal follows 3 or 9.
Example 2
- Input
prices = [2, 4, 6, 8]- Output
[2, 4, 6, 8]- Why
- Prices only rise, so no item gets a discount.
Example 3
- Input
prices = [5, 5, 1]- Output
[0, 4, 1]- Why
- An equal price counts: the first 5 is discounted by the second 5, which in turn is discounted by 1.
Constraints
1 <= prices.length <= 5001 <= prices[i] <= 1000
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan to the right) | O(n²) | O(n) |
| Optimal (monotonic stack) | O(n) | O(n) |
1Brute force (scan to the right)
O(n²)Each item may scan every later item.O(n)The result array.For every item, look at the items after it and subtract the first price that is not larger.
- Copy
pricesintores. - For each i, scan j = i + 1, i + 2, ...; at the first
prices[j] <= prices[i], setres[i] = prices[i] - prices[j]and stop.
class Solution {
public int[] finalPrices(int[] prices) {
int n = prices.length;
int[] res = prices.clone();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (prices[j] <= prices[i]) {
res[i] = prices[i] - prices[j];
break;
}
}
}
return res;
}
}class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
n = len(prices)
res = prices[:]
for i in range(n):
for j in range(i + 1, n):
if prices[j] <= prices[i]:
res[i] = prices[i] - prices[j]
break
return resclass Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();
vector<int> res = prices;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (prices[j] <= prices[i]) {
res[i] = prices[i] - prices[j];
break;
}
}
}
return res;
}
};function finalPrices(prices) {
const n = prices.length;
const res = prices.slice();
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (prices[j] <= prices[i]) {
res[i] = prices[i] - prices[j];
break;
}
}
}
return res;
}2Optimal (monotonic stack)
O(n)Each index is pushed and popped at most once.O(n)The stack can hold all indices when prices strictly increase.Walk left to right with a stack of indices whose discount is still unknown; their prices are strictly increasing from bottom to top. A new price that is less than or equal to the top's price is exactly the discount for that top item, so pop and apply it, repeating while possible, then push the new index.
- Copy
pricesintores; start with an empty stack. - For each j: while the stack is non-empty and
prices[top] >= prices[j], poptopand setres[top] -= prices[j]. - Push j. Items left on the stack at the end keep their full price.
class Solution {
public int[] finalPrices(int[] prices) {
int n = prices.length;
int[] res = prices.clone();
Deque<Integer> stack = new ArrayDeque<>();
for (int j = 0; j < n; j++) {
while (!stack.isEmpty() && prices[stack.peek()] >= prices[j]) {
res[stack.pop()] -= prices[j];
}
stack.push(j);
}
return res;
}
}class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
res = prices[:]
stack = []
for j, p in enumerate(prices):
while stack and prices[stack[-1]] >= p:
res[stack.pop()] -= p
stack.append(j)
return resclass Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();
vector<int> res = prices;
vector<int> st;
for (int j = 0; j < n; j++) {
while (!st.empty() && prices[st.back()] >= prices[j]) {
res[st.back()] -= prices[j];
st.pop_back();
}
st.push_back(j);
}
return res;
}
};function finalPrices(prices) {
const res = prices.slice();
const stack = [];
for (let j = 0; j < prices.length; j++) {
while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[j]) {
res[stack.pop()] -= prices[j];
}
stack.push(j);
}
return res;
}Edge cases to test
- A single item never gets a discount
- Strictly increasing prices: nothing changes
- Equal neighbouring prices: the discount brings the price to 0
- The last item never gets a discount
Hints
Hint 1
For each item you need the first later price that is less than or equal to it: a classic next-smaller-or-equal element query.
Hint 2
Keep a stack of indices still waiting for their discount. When a new price is less than or equal to the price on top, that top item has found its discount.
FAQ
What is the best time complexity for Final Prices With a Special Discount in a Shop?
Optimal (monotonic stack) runs in O(n) time and O(n) extra space. Each index is pushed and popped at most once.
Which pattern does Final Prices With a Special Discount in a Shop use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Final Prices With a Special Discount in a Shop?
Yes. Brute force (scan to the right) takes O(n²) time and O(n) space. For every item, look at the items after it and subtract the first price that is not larger.
Which edge cases should I test for Final Prices With a Special Discount in a Shop?
A single item never gets a discount; Strictly increasing prices: nothing changes; Equal neighbouring prices: the discount brings the price to 0; The last item never gets a discount.