Final Prices With a Special Discount in a Shop

easy monotonic stack array

Problem

In a shop, prices[i] is the price of the i-th item. The shop runs a special offer: when you buy item i, you receive a discount equal to prices[j], where j is the first index after i whose price is less than or equal to prices[i]. If no such later item exists, you pay full price. Return the array of final prices.

This is the textbook next smaller-or-equal element pattern: each item simply waits for the first cheaper (or equally priced) item to its right, and a monotonic stack finds all of those matches in one pass.

Inputprices = [8, 4, 6, 2, 3]

Output[4, 2, 4, 2, 3]

Item 0 (8) is discounted by 4 → pays 4; item 1 (4) by 2 → pays 2; item 2 (6) by 2 → pays 4; items 3 and 4 never see a later price ≤ theirs, so they pay full price.

prices (comma-separated)

def final_prices(prices):
    answer = prices[:]
    stack = []                       # indices waiting for a discount
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] >= price:
            j = stack.pop()
            answer[j] = prices[j] - price
        stack.append(i)
    return answer

function finalPrices(prices) {
  const answer = prices.slice();
  const stack = []; // indices waiting for a discount
  for (let i = 0; i < prices.length; i++) {
    while (stack.length && prices[stack[stack.length - 1]] >= prices[i]) {
      const j = stack.pop();
      answer[j] = prices[j] - prices[i];
    }
    stack.push(i);
  }
  return answer;
}

int[] finalPrices(int[] prices) {
    int[] answer = prices.clone();
    Deque<Integer> stack = new ArrayDeque<>(); // waiting indices
    for (int i = 0; i < prices.length; i++) {
        while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
            int j = stack.pop();
            answer[j] = prices[j] - prices[i];
        }
        stack.push(i);
    }
    return answer;
}

vector<int> finalPrices(vector<int>& prices) {
    vector<int> answer = prices;
    vector<int> stack; // indices waiting for a discount
    for (int i = 0; i < (int)prices.size(); i++) {
        while (!stack.empty() && prices[stack.back()] >= prices[i]) {
            int j = stack.back(); stack.pop_back();
            answer[j] = prices[j] - prices[i];
        }
        stack.push_back(i);
    }
    return answer;
}

Explanation

The brute force answer scans forward from every item looking for the first later price that is ≤ it — O(n²) in the worst case. The key insight is to flip the question around: instead of each item searching for its discount, let each new price announce itself as the discount for every earlier item that is still waiting and costs at least as much.

We keep a stack of indices whose discounts are still unknown. The stack stays strictly increasing by price from bottom to top: whenever a new price x arrives, every index on top with prices[j] ≥ x has just met the first smaller-or-equal price to its right, so we pop it and finalize answer[j] = prices[j] − x. Then x itself joins the stack and waits its turn.

Walk through prices = [8, 4, 6, 2, 3]. Index 0 (8) is pushed. Then 4 arrives: 8 ≥ 4, so item 0 pays 8 − 4 = 4, and index 1 is pushed. Then 6 arrives: 4 < 6, nothing pops, push index 2. Then 2 arrives: 6 ≥ 2 pops item 2 (pays 4), and 4 ≥ 2 pops item 1 (pays 2); push index 3. Finally 3 arrives: 2 < 3, push index 4.

Indices 3 and 4 are still on the stack at the end, which means no later price ever undercut them — they keep their original prices. The final answer is [4, 2, 4, 2, 3], matching the example.

Why is this linear? Each index is pushed exactly once and popped at most once, so the total work across the whole loop is bounded by 2n stack operations. Time is O(n) and the stack itself uses O(n) extra space in the worst case (a strictly increasing price list never pops).

Time: O(n) Space: O(n)