Final Prices with special discount [next smaller element variation, stack]

XXX. Final Prices With a Special Discount

Stack

Array Manipulation

Problem Statement:

Given an array prices where prices[i] is the price of the ith item in a shop, return an array result such that result[i] is the price of the ith item after applying a discount. The discount is the price of the first subsequent item that has a price less than or equal to the current item's price. If there is no such item, the price remains the same.

Algorithm:

The solution uses a stack to efficiently compute discounts:

1. Create a stack to store indices of prices.
2. Iterate through the array:
• While the stack is not empty and the current price is less than or equal to the price at the index stored on top of the stack:
• Pop the top of the stack and update the corresponding price in the result array by subtracting the current price.
• Push the current index onto the stack.
3. Return the updated array as the result.

Complexity:

Time Complexity: O(n), where n is the length of the prices array. Each index is pushed and popped from the stack at most once.
Space Complexity: O(n), for the stack used to store indices.

Java Implementation:

import java.util.Stack;

public class Solution {
    public int[] finalPrices(int[] prices) {
        // Create a copy of prices array to store discounted prices
        int[] result = prices.clone();

        Stack stack = new Stack<>();

        for (int i = 0; i < prices.length; i++) {
            // Process items that can be discounted by current price
            while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
                // Apply discount to previous item using current price
                result[stack.pop()] -= prices[i];
            }
            // Add current index to stack
            stack.add(i);
        }

        return result;
    }
}