Final Prices With a Special Discount in a Shop - Solution & Explanation
Problem Statement
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] <= 1000
Approach Overview
Problem 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 1: Brute Force Approach
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.
Complexity
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.
Approach 2: Using Monotonic Stack
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.
Complexity
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 3: Monotonic Stack
The problem is essentially to find the first element on the right side that is smaller than each element. We can use a monotonic stack to solve this.
We traverse the array prices in reverse order, using the monotonic stack to find the nearest smaller element on the left side of the current element, and then calculate the discount.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array prices.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
Complexity Comparison
| 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. |
| Monotonic Stack | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Final Prices With a Special Discount in a Shop - Leetcode 1475 - Python • NeetCodeIO • 9,333 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Final Prices With a Special Discount in a Shop easy or hard?
Final Prices With a Special Discount in a Shop Python/Java solution
How to solve Final Prices With a Special Discount in a Shop in O(n)?
What is the best approach for Final Prices With a Special Discount in a Shop?
Is Final Prices With a Special Discount in a Shop asked at Google/Amazon/Meta?
What data structure is used in Final Prices With a Special Discount in a Shop?
What is the time complexity of Final Prices With a Special Discount in a Shop?
Ready to solve this problem?
Practice Final Prices With a Special Discount in a Shop with our built-in code editor and test cases.
Practice on FleetCode