Watch 10 video solutions for Final Prices With a Special Discount in a Shop, a easy level problem involving Array, Stack, Monotonic Stack. This walkthrough by NeetCodeIO has 8,607 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 1000Problem Overview: You receive an array prices where each element represents the price of an item in a shop. For every item i, you must find the first item to its right with price less than or equal to prices[i]. That value becomes the discount applied to item i. If no such item exists, the price stays the same. Return the array of final prices.
Approach 1: Brute Force Scan (O(n²) time, O(1) space)
The direct strategy checks every element to the right of each item. For index i, iterate from i + 1 to the end of the array until you find the first value <= prices[i]. Subtract that value and stop searching for that index. If no qualifying value appears, keep the original price. This approach uses simple nested loops and no additional data structures. It works well for small arrays and clearly demonstrates the rule of “first smaller-or-equal value to the right,” but the quadratic time complexity becomes inefficient as n grows.
Approach 2: Monotonic Stack (O(n) time, O(n) space)
The optimal solution uses a decreasing monotonic stack to track indices whose discounts have not been found yet. Traverse the array from left to right. While the stack is not empty and the current price is less than or equal to the price at the index on top of the stack, the current price becomes the discount for that index. Pop the index and subtract the discount from its price. Then push the current index onto the stack.
This works because the stack maintains indices in strictly increasing price order. Once a smaller or equal value appears, it resolves the discount for all higher prices waiting in the stack. Each index is pushed and popped at most once, giving linear time complexity. The pattern is common in stack-based problems that ask for the “next smaller element.”
Using a monotonic structure avoids repeated scanning and ensures every comparison contributes to resolving a discount. The same pattern appears in problems like Next Smaller Element, Daily Temperatures, and Stock Span.
Recommended for interviews: Start by describing the brute force idea to show you understand the rule: find the first smaller-or-equal value to the right. Then move to the monotonic stack optimization. Interviewers typically expect the O(n) solution using a array traversal and stack because it demonstrates pattern recognition and efficient use of data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n²) | O(1) | Useful for understanding the rule or when the input size is very small. |
| Monotonic Stack | O(n) | O(n) | Best general solution. Efficient for large arrays and common in next-smaller-element problems. |