You are given an integer array prices
where prices[i]
is the price of the i<sup>th</sup>
item in a shop.
There is a special discount for items in the shop. If you buy the i<sup>th</sup>
item, then you will receive a discount equivalent to prices[j]
where j
is the minimum index such that j > i
and prices[j] <= prices[i]
. Otherwise, you will not receive any discount at all.
Return an integer array answer
where answer[i]
is the final price you will pay for the i<sup>th</sup>
item of the shop, considering the special discount.
Example 1:
Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Explanation: For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. For items 3 and 4 you will not receive any discount at all.
Example 2:
Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5] Explanation: In this case, for all items, you will not receive any discount at all.
Example 3:
Input: prices = [10,1,1,6] Output: [9,0,1,6]
// Monotonic stack to keep track of indices
// While the stack is not empty and the current price is less than or equal
// to the price at the index stored at the top of the stack
// Apply the discount
// Push the current index onto the stack
// Return the modified answer vector
class Solution {
public:
// vector<int> finalPrices(vector<int>& prices) {
// uint16_t size = prices.size();
// for( uint16_t i = 0; i < size; i++ ){
// for( uint16_t j = i+1; j < size; j++ ){
// if(prices[i]>=prices[j]){
// prices[i]-= prices[j];
// break;
// }
// }
// }
// return prices;
// }
vector<int> finalPrices(vector<int>& prices) {
stack<int> st;
for (int i = 0; i < prices.size(); i++) {
while (!st.empty() && prices[i] <= prices[st.top()]) {
int index = st.top();
st.pop();
prices[index] -= prices[i];
}
st.push(i);
}
return prices;
}
};
Explanation:
- Monotonic Stack:
- We use a stack to keep track of indices where the discount is yet to be applied.
- The stack is monotonic decreasing, meaning it stores indices of prices in decreasing order of their values.
- Efficient Discount Calculation:
- For each price, check the stack:
- If the current price is less than or equal to the price at the top of the stack, apply the discount for the index at the top of the stack.
- Remove that index from the stack since the discount has been applied.
- Push the current index onto the stack.
- For each price, check the stack:
- Time Complexity:
- Each element is pushed onto the stack once and popped from the stack once, resulting in O(n)O(n)O(n) time complexity.
Example Execution:
For prices = [8, 4, 6, 2, 3]
:
- Initialization:
answer = [8, 4, 6, 2, 3]
,stack = []
. - Iteration 1 (
i = 0
):stack = [0]
. - Iteration 2 (
i = 1
):prices[1] = 4 <= prices[stack.top()] = 8
.- Apply discount:
answer[0] = 8 - 4 = 4
. Pop stack.stack = []
. - Push
i = 1
:stack = [1]
.
- Iteration 3 (
i = 2
):stack = [1, 2]
(no discount applied yet). - Iteration 4 (
i = 3
):prices[3] = 2 <= prices[stack.top()] = 6
.- Apply discount:
answer[2] = 6 - 2 = 4
. Pop stack.stack = [1]
. prices[3] = 2 <= prices[stack.top()] = 4
.- Apply discount:
answer[1] = 4 - 2 = 2
. Pop stack.stack = []
. - Push
i = 3
:stack = [3]
.
- Iteration 5 (
i = 4
):stack = [3, 4]
(no discount applied yet).
Final answer = [4, 2, 4, 2, 3]
.
Space Complexity:
- The stack stores at most nnn indices, so the space complexity is O(n)O(n)O(n).