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.
This approach involves checking each item's price and looking for the first subsequent item that has a lesser or equal price. We will iterate through the prices array and for each price, find the discount by iterating from the current index to the end of the array.
The function iterates through each price and for each price, it looks through subsequent prices to find the first one that is less than or equal to the current price. Once found, it subtracts that price from the current price.
Time Complexity: O(n^2) where n is the number of items in the prices array because for each price, you may need to check all subsequent prices.
Space Complexity: O(1) as we only use a fixed amount of extra space.
This optimized approach leverages a stack to efficiently track and find the next lower or equal price for each item. By using a stack, we can achieve the required result in linear time, processing each price only once while maintaining potential discounts.
This solution uses a monotonic stack to keep track of indices. As we iterate over the array, whenever we find a price that is less than or equal to the price at the top of the stack, we use it as a discount for prices in the stack and then pop it.
Time Complexity: O(n), since each element is pushed and popped from the stack at most once.
Space Complexity: O(n), for storing the indices in the stack.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) where n is the number of items in the prices array because for each price, you may need to check all subsequent prices. |
| Using Monotonic Stack | Time Complexity: O(n), since each element is pushed and popped from the stack at most once. |
| 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. |
Final Prices With a Special Discount in a Shop - Leetcode 1475 - Python • NeetCodeIO • 8,607 views views
Watch 9 more video solutions →Practice Final Prices With a Special Discount in a Shop with our built-in code editor and test cases.
Practice on FleetCode