Compute the final price of each item after applying the first discount price to its right that is less than or equal to it.
You are given an array of item prices in a shop. For each price at index , apply a special discount using the first price to the right of that is less than or equal to it. If no such price exists, the item gets no discount.
Return the list of final prices after all discounts are applied.
You should preserve the order of items and compute each final price independently based on the rule above.
Input Format
- A list of integers
prices, whereprices[i]is the price of the -th item. - Each item is discounted using the first later price
prices[j]such thatj > iandprices[j] <= prices[i]. - If no such
jexists, the discount is0.
Output Format
- Return a list of integers of the same length as
prices. - The -th value is
prices[i] - discount_i.
Constraints
- The solution should be efficient enough for large arrays.
Example 1
Input
prices = [8,4,6,2,3]
Output
[4,2,4,2,3]
Explanation
- 8 gets a discount of 4, so final price is 4.
- 4 gets a discount of 2, so final price is 2.
- 6 gets a discount of 2, so final price is 4.
- 2 has no smaller-or-equal price to its right, so it stays 2.
- 3 has no smaller-or-equal price to its right, so it stays 3.
Example 2
Input
prices = [1,2,3,4,5]
Output
[1,2,3,4,5]
Explanation
No item has a later price that is less than or equal to it, so no discounts apply.
Show 1 more example
Example 3
Input
prices = [10,1,1,6]
Output
[9,0,1,6]
Explanation
- 10 gets a discount of 1 from the first 1 on the right.
- The first 1 gets a discount of 1 from the next 1, so it becomes 0.
- The second 1 has no later price less than or equal to it.
- 6 has no later price less than or equal to it.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.