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] <= 1000This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Final Prices With a Special Discount in a Shop • Fraz • 6,225 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 FleetCodePractice this problem
Open in Editor