Final Prices With a Special Discount in a Shop

Easy
382.

Final Prices With a Special Discount in a Shop

Final Prices With a Special Discount in a Shop is an easy coding problem on arrays, stack and monotonic stack, asked in Amazon, Adobe and Dream11 interviews.

You are given an array prices where prices[i] is the price of the i-th item.

Buying item i earns a discount equal to prices[j], where j is the smallest index greater than i with prices[j] <= prices[i]. If no such j exists, there is no discount.

Return the array of prices actually paid.

Example 1

Input
prices = [8,4,6,2,3]
Output
[4,2,4,2,3]

Example 2

Input
prices = [1,2,3,4,5]
Output
[1,2,3,4,5]
Explanation
No item has a cheaper item after it.

Example 3

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

Constraints

  • 1 <= prices.length <= 40
  • 1 <= prices[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @return {number[]}
 */
var finalPrices = function(prices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Final Prices With a Special Discount in a Shop — Solution

Final Prices With a Special Discount in a Shop solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Final Prices With a Special Discount in a Shop is an easy coding problem on arrays, stack and monotonic stack, asked in Amazon, Adobe and Dream11 interviews.

Problem statement

You are given an array prices where prices[i] is the price of the i-th item.

Buying item i earns a discount equal to prices[j], where j is the smallest index greater than i with prices[j] <= prices[i]. If no such j exists, there is no discount.

Return the array of prices actually paid.

Example 1

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]

Example 2

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: No item has a cheaper item after it.

Example 3

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

Constraints

  • 1 <= prices.length <= 40
  • 1 <= prices[i] <= 1000

Hints for Final Prices With a Special Discount in a Shop

  1. Hint 1

    This is the classic "next smaller or equal element" problem.

  2. Hint 2

    Keep a stack of indices whose discount is still unknown, with prices increasing from bottom to top.

  3. Hint 3

    When a new price arrives, it discounts every index on the stack whose price is at least as large.

How to solve Final Prices With a Special Discount in a Shop

Next smaller-or-equal element with a monotonic stack: indices waiting for a discount sit on the stack with increasing prices; a new price pays off every index whose price is at least as large.

Approach

  1. For each i, while the stack top's price >= prices[i], pop j and set out[j] = prices[j] - prices[i].
  2. Push i.

Why it works

The first later index with a price ≤ the current one is by definition the first that pops it; indices never popped keep their full price.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Use >=, not > — an equal price counts as a discount.

Reference solution

Python

def finalPrices(prices):
    out = list(prices)
    stack = []
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] >= price:
            j = stack.pop()
            out[j] = prices[j] - price
        stack.append(i)
    return out

Java

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

C++

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

JavaScript

var finalPrices = function(prices) {
    const out = prices.slice();
    const stack = [];
    for (let i = 0; i < prices.length; i++) {
        while (stack.length > 0 && prices[stack[stack.length - 1]] >= prices[i]) {
            const j = stack.pop();
            out[j] = prices[j] - prices[i];
        }
        stack.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure