Final Prices With a Special Discount in a Shop

LeetCode 1570 | Difficulty: Easy

Easy

Problem Description

You are given an integer array prices where prices[i] is the price of the i^th item in a shop.

There is a special discount for items in the shop. If you buy the i^th 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 i^th item of the shop, considering the special discount.

Example 1:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4.
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2.
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4.
For items 3 and 4 you will not receive any discount at all.

Example 2:

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.

Example 3:

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

Constraints:

- `1 <= prices.length <= 500`

- `1 <= prices[i] <= 1000`

Topics: Array, Stack, Monotonic Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

---

Solutions

Solution 1: C# (Best: 267 ms)

Metric	Value
Runtime	267 ms
Memory	42.2 MB
Date	2022-02-07

Solution

public class Solution {
    public int[] FinalPrices(int[] prices) {
        Stack<int> s = new Stack<int>();
    for (int i = 0; i < prices.Length; i++)
    {
        while (s.Count > 0 && prices[s.Peek()] >= prices[i])
        {
            prices[s.Peek()] = prices[s.Peek()] - prices[i];
            s.Pop();
        }
        s.Push(i);
    }
    return prices;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use brute force: For the ith item in the shop with a loop find the first position j satisfying the conditions and apply the discount, otherwise, the discount is 0.