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.
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 <= 5001 <= prices[i] <= 1000In #1475 Final Prices With a Special Discount in a Shop, each item's price may receive a discount equal to the first item to its right that has a price less than or equal to it. The challenge is efficiently finding this next qualifying price for every element in the array.
A straightforward method is to check each element with all elements to its right, but this leads to O(n^2) time complexity. A more optimal strategy uses a monotonic stack. By iterating through the prices and maintaining a stack of indices whose discounts have not yet been determined, we can quickly identify when the current price satisfies the discount condition for previous items.
Whenever the current price is less than or equal to the price at the index on the top of the stack, we apply the discount and pop that index. This ensures each element is pushed and popped at most once, resulting in an efficient O(n) time solution with O(n) auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (Check all elements to the right) | O(n^2) | O(1) |
| Monotonic Stack | O(n) | O(n) |
Fraz
Use these hints if you're stuck. Try solving on your own first.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A monotonic stack maintains elements in a specific order, allowing quick identification of the next smaller or equal value. This avoids repeated comparisons and ensures each element is processed only once, improving efficiency.
Problems involving monotonic stacks and next smaller elements are common in technical interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the pattern frequently appears in interview questions.
A stack is the most suitable data structure for this problem. Specifically, a monotonic stack helps efficiently find the next smaller or equal element to the right for each price, which determines the discount.
The optimal approach uses a monotonic stack to track indices of prices that have not yet received a discount. As you traverse the array, whenever a smaller or equal price appears, it becomes the discount for previous items. This reduces the time complexity to O(n).