Final Prices With a Special Discount in a Shop

Leetcode Problem:

• Final Prices With a Special Discount in a Shop

Summary

• Given an integer array prices where prices[i] is the price of the ith item in a shop, find the final price for each item considering a special discount.

Approach

• The solution uses a stack to keep track of the prices of items that have not been discounted yet
• It iterates through the prices array in reverse order, and for each item, it checks if there is a smaller item in the stack that can provide a discount
• If a discount is found, it is applied to the current item, and the updated price is pushed onto the stack
• If no discount is found, the current price is pushed onto the stack as is.

Complexity

• O(n), where n is the number of items in the prices array, because each item is processed once.

Explanation

• The solution uses a stack to efficiently find the smallest price that can provide a discount for each item
• It starts by iterating through the prices array in reverse order, and for each item, it checks if there is a smaller item in the stack that can provide a discount
• If a discount is found, it is applied to the current item, and the updated price is pushed onto the stack
• This process continues until the stack is empty, at which point the current item's price is pushed onto the stack as is
• This approach ensures that each item is processed only once and that the stack is always in the correct order to find the smallest price that can provide a discount.

Solution Code:

class Solution {
public:
    vector st;
    vector finalPrices(vector& prices) {
        for(int i = prices.size() - 1; i >= 0 ; i--){
            while(st.size() != 0 && st.back() > prices[i]){
                st.pop_back();
            }
            if(st.size() == 0){
                st.push_back(prices[i]);
            } else{
                prices[i] -= st.back();
                st.push_back(prices[i] + st.back());
            }
        }
        return prices;
    }
};