weeklychallenge

Python solution to the weekly challenge 325 task 2

Yitzchak Scott-Thoennes

Yitzchak Scott-Thoennes

— 1 min read

Task 2: Final Price:

You are given an array of item prices.

Write a script to find out the final price of each items in the given array.

There is a special discount scheme going on. If there’s an item with a lower or equal price later in the list, you get a discount equal to that later price (the first one you find in order).

A brute force approach is simply to, for each price in the list, search for the first later price that is not greater.

But this has quadratic complexity (O(n^2)). This can be reduced to O(n log n) by instead going through the list backwards, as you go you keeping a sorted list of potential discounts that may apply to earlier prices in the list.

Ideally for this you'd use a data type that is an easily searchable/iterable set, such as a Judy1 array (which is really a set, stored as a tree). Unfortunately, the full Judy interface seems to be only available from the Python 2 pyjudy; the Python 3 judy interface is minimal. So I will just use a list, kept in sorted order and searched using bisect.

sale_prices = []
seen_prices = []
for price in reversed(prices):

First we find where the current price would belong in the seen list, using bisect_right; the element before that (if any) is our discount.

    seen_price_index = bisect.bisect_right(seen_prices, price)
    discount = seen_prices[seen_price_index-1] if seen_price_index > 0 else 0

Now any previously encountered prices greater than the current price are irrelevant, so we can discard them, and add this price:

    if seen_price_index == 0 or seen_prices[seen_price_index-1] != price:
        seen_prices[seen_price_index:] = [price]

Here, the if only serves to prevent (harmless) duplicate prices in our list; it could be omitted and just do the assignment. If we'd originally done a bisect_left, the if would also be unneeded, but the discount code would be slightly more complex.

And insert the sale price:

sale_prices.insert(0, price - discount)

If preferred, this could be appended instead, and the list reversed to restore the original prices order.

full script
in Perl, for comparison

See you next week.

Read more