## DEV Community is a community of 800,290 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

TK

Posted on • Originally published at leandrotk.github.io

# Algorithms Problem Solving: 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.