Posted on

Final Prices With a Special Discount in a Shop

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:

  1. 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.
  2. 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.
  3. 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).