Final prices with a special discount in a shop

Array Stack Monotonic Stack

84.0% acceptance

Feb 25, 2026

2902

152

You are given an integer array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all. Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
    let n = prices.len();
    let mut result = prices.clone();
    let mut stack: Vec<usize> = Vec::new(); // monotone stack (non-decreasing prefix)
    for i in 0..n {
      while let Some(&top) = stack.last() {
        if prices[i] <= prices[top] {
          result[top] -= prices[i];
          stack.pop();
        } else {
          break;
        }
      }
      stack.push(i);
    }
    result
  }
}