1475. Final Prices With a Special Discount in a Shop

[Problem]

Array Stack Monotonic Stack

---

Intuition

• The problem requires calculating the final prices after applying a discount.
• The discount is the next smaller or equal value to the current price.
• To find this, we use a monotonic stack to track indices where discounts may be applied.

Approach

1. Brute Force [TC: O(n^2)]

• Traverse the array
• Take the current index
• Find potential discount, if found, apply it

Code(Brute-Force):

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;

        // modifying inputs is not a good practice, hence we clone it
        int[] result = prices.clone();

        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                // find next immediate minimum element (discount)
                if(prices[j] <= prices[i]){
                    // apply discount
                    result[i] = prices[i] - prices[j];
                    break;
                }
            }
        }
        return result;
    }
}

2. Using Stack [TC: O(n)]

• Stack Initialization: Use a stack to store indices of prices that may get discounted in the future.
• Traversal: Iterate through the prices array.
  • If the current price is less than or equal to the price at the top of the stack, pop the index and subtract the current price (valid discount applied).
  • Else, push the current index to the stack, that means can’t find discount as of now.
• Return the modified result array.
• The stack ensures we process each element efficiently in a monotonic decreasing order, allowing for quick discount application.

Code

class Solution {
    public int[] finalPrices(int[] prices) {
        // Monotonic stack
        Stack<Integer> stack = new Stack<>();
        int[] result = prices.clone();

        for (int i = 0; i < prices.length; i++) {
            // Pop indices and apply discount when the criteria are met
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                int popIndex = stack.pop();
                result[popIndex] -= prices[i];
            }
            // Push current index for potential future discount check
            stack.push(i);
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n)
  • Each price is pushed and popped from the stack once.
  • Hence total operations: 2*n = O(n)
• Space Complexity: O(n)
  • The stack in worst case has n indices