Discount for prices
This post is part of the Algorithms Problem Solving series.
Problem description
This is the Final Prices With a Special Discount in a Shop problem. The description looks like this:
Given the
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 array where the ith
element is the
final price you will pay for the ith
item of
the shop considering the special discount.
Examples
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]
Solution
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
price
.
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.
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!