Solution Explanation:

This problem asks to calculate the final price of each item after applying a special discount. The discount for the ith item is the price of the first item with a lower price found at an index greater than i. A monotonic stack provides an efficient solution.

Approach:

We iterate through the prices array from right to left. A monotonic decreasing stack is used to store the prices encountered so far. For each price, we check the stack:

1. Pop from Stack: As long as the stack is not empty and the top of the stack (representing a previously encountered price) is greater than the current price, we pop elements from the stack. This is because those popped prices will never be a valid discount for any future item (since the current price is smaller and comes later).

2. Apply Discount (if applicable): If the stack is not empty after popping, the top of the stack is the nearest smaller price to the right. We subtract this top price from the current price to apply the discount.

3. Push onto Stack: Finally, the current price is pushed onto the stack to maintain the decreasing order.

Time Complexity: O(n) - Each element is pushed and popped at most once from the stack. The iteration through the array is linear.

Space Complexity: O(n) - In the worst-case scenario, the stack could potentially store all elements of the prices array.

Code Implementation in Various Languages:

The core logic remains the same across all languages: iterate in reverse order, use a stack to maintain decreasing prices, pop greater elements, apply discount if a smaller element is found, and push the current element. Here's the detailed code in multiple languages:

Python:

def finalPrices(prices):
    stack = []
    for i in range(len(prices) - 1, -1, -1):
        price = prices[i]
        while stack and stack[-1] > price:
            stack.pop()
        discount = stack[-1] if stack else 0
        prices[i] -= discount
        stack.append(price)
    return prices

Java:

import java.util.Deque;
import java.util.ArrayDeque;
 
class Solution {
    public int[] finalPrices(int[] prices) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = prices.length - 1; i >= 0; i--) {
            int price = prices[i];
            while (!stack.isEmpty() && stack.peek() > price) {
                stack.pop();
            }
            int discount = stack.isEmpty() ? 0 : stack.peek();
            prices[i] -= discount;
            stack.push(price);
        }
        return prices;
    }
}

C++:

#include <vector>
#include <stack>
 
class Solution {
public:
    std::vector<int> finalPrices(std::vector<int>& prices) {
        std::stack<int> stack;
        for (int i = prices.size() - 1; i >= 0; i--) {
            int price = prices[i];
            while (!stack.empty() && stack.top() > price) {
                stack.pop();
            }
            int discount = stack.empty() ? 0 : stack.top();
            prices[i] -= discount;
            stack.push(price);
        }
        return prices;
    }
};

JavaScript:

var finalPrices = function(prices) {
    let stack = [];
    for (let i = prices.length - 1; i >= 0; i--) {
        let price = prices[i];
        while (stack.length > 0 && stack[stack.length - 1] > price) {
            stack.pop();
        }
        let discount = stack.length === 0 ? 0 : stack[stack.length - 1];
        prices[i] -= discount;
        stack.push(price);
    }
    return prices;
};

//Other languages like Go, TypeScript, Rust, and PHP would follow similar structures, using their respective stack implementations. The core algorithm remains consistent.