Final Prices With a Special Discount in a Shop

class Solution {
public:
    vector<int> reducedPrices(vector<int>& inputPrices) {
        vector<int> discountedPrices = inputPrices;
        stack<int> indicesStack;

        for (int index = 0; index < inputPrices.size(); index++) {
            while (!indicesStack.empty() && inputPrices[indicesStack.top()] >= inputPrices[index]) {
                discountedPrices[indicesStack.top()] -= inputPrices[index];
                indicesStack.pop();
            }
            indicesStack.push(index);
        }

        return discountedPrices;
    }
};

The provided C++ solution implements a function reducedPrices to calculate the final prices of items after applying a special discount. Each item’s discount is the price of the next item that is cheaper or equal in value and appears later in the list. If no such item exists, no discount is applied for that item.

The function takes a vector inputPrices as input, which contains the original prices of the items. It initializes discountedPrices with the original prices and uses a stack indicesStack to keep track of indices of prices that might be eligible for a discount.

Working mechanism:

• Iterates over each price using index.
• Checks elements in the stack; if the current price at index is less than or equal to the price at the index stored at the top of the stack, it applies the discount to the price in discountedPrices corresponding to the top of the stack and then removes the index from the stack.
• Pushes the current index to the stack for potential future discounts.

This approach ensures each price is compared with following prices only once, hence the function operates efficiently with a time complexity essentially linear to the number of items, due to the properties of stack operations (push and pop).

At the end of the loop, discountedPrices containing all discounted prices is returned. This vector represents the final prices of items where each eligible item has been discounted based on its qualifying subsequent lower or equal priced item.

class Solution {

    public int[] applyDiscounts(int[] costs) {
        // Duplicate the costs array to hold the discounted values
        int[] discountedCosts = costs.clone();

        Stack<Integer> indexStack = new Stack<>();

        for (int index = 0; index < costs.length; index++) {
            // Check and apply discounts as pertinent
            while (!indexStack.isEmpty() && costs[indexStack.peek()] >= costs[index]) {
                // Deduct the discount from the applicable product
                discountedCosts[indexStack.pop()] -= costs[index];
            }
            // Track current product index
            indexStack.push(index);
        }

        return discountedCosts;
    }
}

The provided Java solution addresses the problem of applying a special discount to a list of prices in a shop. Each price can potentially be discounted based on the next lower or equal price coming after it in the list. The algorithm makes use of a stack to efficiently manage and apply these discounts.

The core functionality is implemented in the applyDiscounts method of the Solution class. Here's a breakdown of the method:

1. Clone the original costs array to discountedCosts which will store the final prices after discounts are applied.
2. Initialize a Stack (indexStack) that will hold indexes of the prices.
3. Iterate through each price in the costs array using a for loop.
4. Inside the loop, use another loop to:
   • Check if the stack is not empty and the current price is less than or equal to the price at the index on the top of the stack.
   • If the condition is true, update the price in discountedCosts at the top index of the stack by subtracting the current price (the discount).
   • Pop the index from the stack.
5. Push the current index onto the stack to track it for potential future discounts.
6. Return the discountedCosts array containing prices after discounts were applied.

This method efficiently computes the final prices by using stack operations that provide O(1) time complexity for push and pop operations, leading to an overall time complexity of O(n), where n is the number of items in the costs array. This approach ensures that each price is processed in a linear pass, making it optimal for this type of discount application where the next least or equal price affects the discounting of previous prices.

class Solution:
    def calculateDiscountedPrices(self, prices: List[int]) -> List[int]:
        # Container for discounted price calculations
        discountedPrices = prices.copy()
        
        # Use a deque to manage indices for processing discounts
        indicesStack = deque()

        for index in range(len(prices)):
            # Check possible discounts with previous kept indices
            while indicesStack and prices[indicesStack[-1]] >= prices[index]:
                # Apply available discount to the price at the popped index
                discountedPrices[indicesStack.pop()] -= prices[index]
            # Store current index to potentially use for future discounts
            indicesStack.append(index)
        
        return discountedPrices

This Python solution is designed to apply a special discount strategy to a list of prices in a shop. The function calculateDiscountedPrices efficiently computes the final prices after applying the necessary discounts. Here's how the algorithm works:

• Start by creating a copy of the original list, discountedPrices, which will hold the final discounted values.
• Use a deque, named indicesStack, to keep track of the indices while iterating through the price list. This helps in determining when and where discounts can be applied.
• Iterate over the prices using a loop. For each price, the loop checks if there's a discount possibility by referencing the indices stored in indicesStack.
• If the current price is lower than or equal to the price at the last index stored in indicesStack, it means a discount can be applied to the item represented by that stored index. The discount is the value of the current price, and it's subtracted from the corresponding price in discountedPrices.
• After processing possible discounts for the current price, store its index in indicesStack for potential future discounts.
• Once all indices are processed, the list discountedPrices with applied discounts is returned.

This method leverages a monotonic stack approach by handling indices in the indicesStack to keep track of potential discounts, ensuring an efficient run-time complexity.