Problem Statement (LeetCode 1475)

You are given an integer array prices where prices[i] is the price of the $i^{\text{th}}$ item in a shop. There is a special discount for items in the shop: if you buy the $i^{\text{th}}$ item, you receive a discount equivalent to prices[j], where j is the minimum index such that j > i and prices[j] <= prices[i]. If no such index j exists, you pay the full price without any discount.

Return an integer array answer where answer[i] is the final price you will pay for the $i^{\text{th}}$ item after applying the special discount.

Examples

Example 1:
Input: prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]
Explanation:
- Item 0 (price 8) receives a discount of prices[1] = 4 -> 8 - 4 = 4.
- Item 1 (price 4) receives a discount of prices[3] = 2 -> 4 - 2 = 2.
- Item 2 (price 6) receives a discount of prices[3] = 2 -> 6 - 2 = 4.
- Items 3 and 4 have no subsequent element <= their price.

Example 2:
Input: prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]

Example 3:
Input: prices = [10, 1, 1, 6]
Output: [9, 0, 1, 6]

Algorithmic Intuition: Next Smaller or Equal Element via Monotonic Stack

Finding the first subsequent index j > i such that prices[j] <= prices[i] is the classic next smaller or equal element problem. Instead of scanning rightward from every index $i$ in $\mathcal{O}(n^2)$ time, we maintain a monotonic stack storing indices of items that are still waiting for their discount.

• Because any incoming price prices[i] that is less than or equal to the price at stack.top() immediately resolves the discount for stack.top(), the indices remaining inside the stack always correspond to strictly increasing prices from bottom to top.
• When examining prices[i], we repeatedly pop every index prevIdx from the top of the stack satisfying prices[i] <= prices[prevIdx] and subtract prices[i] from prices[prevIdx].
• Finally, we push index i onto the stack so it can await its own potential future discount.

Step-by-Step Execution Trace

Tracing prices = [8, 4, 6, 2, 3] across all 5 iterations:

C++ Implementation

#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<int> st;
        const int n = static_cast<int>(prices.size());

        for (int i = 0; i < n; i++) {
            // Resolve discounts for all pending items with price >= prices[i]
            while (!st.empty() && prices[i] <= prices[st.top()]) {
                int prevIndex = st.top();
                st.pop();
                prices[prevIndex] -= prices[i];
            }
            st.push(i);
        }

        return prices;
    }
};

TypeScript Implementation

export function finalPrices(prices: number[]): number[] {
  const result = [...prices];
  const stack: number[] = [];

  for (let i = 0; i < result.length; i++) {
    while (stack.length > 0 && result[i] <= result[stack[stack.length - 1]]) {
      const prevIndex = stack.pop()!;
      result[prevIndex] -= result[i];
    }
    stack.push(i);
  }

  return result;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n)$. Every index from $0$ to $n - 1$ is pushed onto the monotonic stack exactly once and popped at most once, resulting in at most $2n$ stack operations across the entire loop.
• Space Complexity: $\mathcal{O}(n)$ auxiliary space in the worst case (such as a strictly increasing price array like [1, 2, 3, 4, 5]), where all $n$ indices remain on the stack until termination.