Algorithms Problem Solving: Discount for prices
Tags: algorithms, python, computerscience, interview
Published: 2020-06-23 11:50:49

---
title: Algorithms Problem Solving: Discount for prices
published: true
description: Solving algorithms problems with TK
tags: algorithms, python, computerscience, interview
cover_image: https://leandrotk.github.io/tk/series/algorithms-problem-solving/assets/money.jpg
canonical_url: https://leandrotk.github.io/tk/series/algorithms-problem-solving/discount-for-prices.html
series: Algorithms Problem Solving Series
---

This post is part of the [Algorithms Problem Solving](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html) series.

## Problem description

This is the [Final Prices With a Special Discount in a Shop](https://leetcode.com/problems/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

```python
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.

```python
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](https://leandrotk.github.io/tk/2017/09/learning-python-from-zero-to-hero/index.html)
- [Algorithms Problem Solving Series](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html)
- [Stack Data Structure](https://leandrotk.github.io/tk/2020/01/stack-data-structure/index.html)
- [Queue Data Structure](https://leandrotk.github.io/tk/2020/01/queue-data-structure/index.html)
- [Linked List](https://leandrotk.github.io/tk/2020/02/linked-list/index.html)
- [Tree Data Structure](https://leandrotk.github.io/tk/2020/02/tree-data-structure/index.html)