Prices After the Next Discount
Problem
A shop lists item prices in shelf order. Buying item i earns a discount equal to the price of the first item to its right whose price is less than or equal to prices[i]. If no such item exists, there is no discount. Return the price actually paid for every item.
Examples
Input: prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]
Why: 8 is discounted by 4, 4 and 6 are both discounted by 2, and 2 and 3 have no cheaper item after themInput: prices = [10, 1, 1, 6]
Output: [9, 0, 1, 6]
Why: an equal price counts, so the first 1 is discounted by the second 1Input: prices = [1, 2, 3, 4, 5]
Output: [1, 2, 3, 4, 5]
Why: edge case, rising prices never meet a cheaper item to the rightHints
0 / 3
For every item you need the first price to its right that is not larger. Checking each item against everything after it is quadratic. Which items are still waiting for their discount at any moment?
An item stops waiting as soon as a price at or below its own appears. The items still waiting always have rising prices from bottom to top, so a new price settles them from the top down.
Keep a stack of indices. For each new price, pop every index whose price is greater than or equal to it and subtract the new price from that item. Then push the new index. Items left on the stack keep their full price.
Solution
This is the next smaller element scan, the same one Largest Rectangle runs to find where each bar stops. Indices wait on a stack with rising prices, and the first price at or below an item's own pops it and fixes its discount. An item that is never popped had no cheaper item to its right, so it keeps its price, which is why the result starts as a copy of the input. Every index is pushed and popped at most once, so time is O(n) and space is O(n).
def final_prices(prices):
paid = prices[:] # no discount unless one is found
stack = [] # waiting indices, prices rising upward
for i, p in enumerate(prices):
while stack and prices[stack[-1]] >= p: # p is the first price at or below theirs
j = stack.pop()
paid[j] = prices[j] - p
stack.append(i)
return paid
print(final_prices([8, 4, 6, 2, 3])) # -> [4, 2, 4, 2, 3]
print(final_prices([10, 1, 1, 6])) # -> [9, 0, 1, 6]
print(final_prices([1, 2, 3, 4, 5])) # -> [1, 2, 3, 4, 5]Stuck on the idea rather than the code? Largest Rectangle covers it.