Code Logo

Final Prices With Discount

Published at23 Jul 2026
Created by
Easy 0 views
Like0

You are given an array of prices for items in a store. For each item, you receive a discount equal to the first lower or equal price that appears to its right. If no such discount exists, you pay the full price. Return the final price after applying the discount.

A monotonic stack solves this in O(n) time. Iterate through the prices. While the stack is not empty and the current price is less than or equal to the price at the top of the stack, pop the top and apply the discount (subtract the current price from the popped price). Then push the current index onto the stack. At the end, any remaining indices in the stack have no discount.

For example, [8, 4, 6, 2, 3] → final prices are [4, 2, 4, 2, 3]. Item 0 gets 4 discount, item 1 gets 2 discount, item 2 gets 2 discount, items 3 and 4 get no discount.

This problem tests understanding of stack operations in a practical context. The stack-based approach is the standard solution and runs in linear time. It is commonly asked in entry-level interviews to assess fundamental data structure knowledge.

The monotonic stack tracks indices of items waiting for a discount. When a lower or equal price arrives, it triggers discounts for all items in the stack that have a higher price. This is O(n) because each index enters and leaves the stack once. The same pattern is used in the Next Greater Element problem, making this a gentle introduction to monotonic stacks.

Example Input & Output

Example 1
Input
[1,2,3,4,5]
Output
[1,2,3,4,5]
Explanation

No discounts since ascending.

Example 2
Input
[5,5,5,5]
Output
[0,0,0,5]
Explanation

Each gets discount from the next equal.

Example 3
Input
[8,4,6,2,3]
Output
[4,2,4,2,3]
Explanation

8 discount 4, 4 discount 2, 6 discount 2, rest no discount.

Algorithm Flow

Recommendation Algorithm Flow for Final Prices With Discount
Recommendation Algorithm Flow for Final Prices With Discount

Solution Approach

Use a stack of indices. For each price, while stack non-empty and current price <= price at top of stack, pop and apply discount. Push current index. Remaining indices get no discount.

function solution(prices) {
  var stack = [], i;
  for (i = 0; i < prices.length; i++) {
    while (stack.length && prices[i] <= prices[stack[stack.length-1]])
      prices[stack.pop()] -= prices[i];
    stack.push(i);
  }
  return prices;
}

Time O(n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[i] <= prices[stack.peek()])
                prices[stack.pop()] -= prices[i];
            stack.push(i);
        }
        return prices;
    }
}