This post is part of the Algorithms Problem Solving series.
This is the Final Prices With a Special Discount in a Shop problem. The description looks like this:
the price of the
ith item in a shop. There is a
special discount for items in the shop, if you buy
ith item, then you will receive a discount
the minimum index such that
j > i and
prices[j] <= prices[i], otherwise, you
will not receive any discount at all.
Return an array where the
ith element is the
final price you will pay for the
ith item of
the shop considering the special discount.
Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5] Input: prices = [10,1,1,6] Output: [9,0,1,6]
The solution idea is to iterate over the
prices list and
for each price, try to get a discount. If it has, apply the discount.
Otherwise, the price stays the same.
I built a
get_discount function passing the
prices list, the
index, and the current
To get the discount, we need to iterate through the list from the
current index + 1 to the end of the
prices list. If we
find the first price that satisfies the rule, just return this price.
If we didn't find any other price, just return 0.
Then we just need to apply the discount by subtracting the
discount from the current
price and add to
the new list of prices with discount.
def final_prices(prices): result =  for index, price in enumerate(prices): discount = get_discount(prices, index, price) result.append(price - discount) return result def get_discount(prices, index, price): for other_price in prices[index + 1:]: if other_price <= price: return other_price return 0
We could also modify the
prices list in-place.