Final Prices With a Special Discount

Problem

You are given an array prices where prices[i] is the price of the i-th item in a shop. There is a special discount: for item i you receive a discount equal to prices[j] — the price of the first later item j > i whose price is less than or equal to prices[i]. If no such j exists, you pay full price. Return an array where the i-th value is the final price paid for item i.

Constraints

• 1 ≤ prices.length ≤ 500
• 1 ≤ prices[i] ≤ 1000

Approach — Monotonic Stack

This is a Monotonic Stack problem. The idea: scan once and keep a stack whose order stays meaningful, popping elements as soon as a later value resolves them. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def finalPrices(self, prices):
        res = prices[:]
        st = []
        for i, p in enumerate(prices):
            while st and prices[st[-1]] >= p:
                res[st.pop()] -= p
            st.append(i)
        return res

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] res = prices.clone();
        // Monotonic stack of indices whose prices stay non-increasing.
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // prices[i] is the first later price <= the items on top.
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                int j = stack.pop();
                res[j] = prices[j] - prices[i];
            }
            stack.push(i);
        }
        return res;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.