Abstract / Summary

Given a list of prices and a list of discounts each discount applies to the next higher or equal price so the final prices are adjusted accordingly.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 84% (400k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method finalPrices that computes the net price a customer pays for each item after applying a single-use discount rule. The discount for an item is the price of the first subsequent item that is less than or equal to the current item's price. The method processes the input list sequentially, determines the applicable discount for each position, and yields the resulting price one by one.

Core Logic

The method begins by iterating over the indices of the input list prices. For each index i it stores the original price in a temporary variable pay.

for i in range(len(prices)):
    pay = prices[i]

A nested loop then scans the elements that follow the current index. The inner loop stops as soon as it encounters a price that satisfies the discount condition (pay >= prices[j]). When such a price is found, the discount is applied by subtracting the found price from pay, and the inner loop terminates immediately with a break.

for j in range(i + 1, len(prices)):
    if  pay >= prices[j]:
        # discount
        pay -= prices[j]
        break

After the inner loop finishes-whether a discount was applied or not-the method yields the final value of pay. Because yield is used, the method returns a generator rather than a concrete list, allowing the caller to retrieve results lazily.

yield pay

Edge-Case Handling

When the input list contains only a single element, the outer loop executes once, the inner loop has no range to iterate over, and the original price is yielded unchanged. This correctly reflects the rule that no discount can be applied when there are no subsequent items.

If the list is strictly decreasing, each element finds a smaller price immediately after it, so the inner loop always triggers the discount on the first iteration. The code correctly subtracts the next price and proceeds to the next outer iteration.

When two consecutive items have equal prices, the condition pay >= prices[j] evaluates to true, causing the discount to be applied using the equal price. This matches the specification that a discount may be taken from an item of equal cost.

If no later price satisfies the discount condition-such as when the current price is the smallest among the remaining items-the inner loop completes without entering the if block. In that case pay remains unchanged and the original price is yielded, which is the intended behavior when no discount is available.

Performance Optimizations

The early termination of the inner loop via break is a key optimization. By stopping the search as soon as the first qualifying discount is found, the algorithm avoids unnecessary comparisons with later elements, reducing the amount of work performed for each outer iteration.

The use of a generator (yield) instead of constructing an intermediate list provides a memory-efficient execution path. Results are produced on demand, which can be advantageous when the caller processes the output incrementally or when the input list is large. This approach minimizes the peak memory footprint because only the current pay value needs to be stored at any moment.

Overall, the combination of early exit from the inner search and lazy result production yields a solution that balances computational effort with memory usage while faithfully implementing the discount rule.

Imagine you have a long row of toys, each with a price tag on it. You want to buy all of them, but there is a special sale happening for each toy. To find the final price of a toy, you walk down the line and look at all the toys that come after it. As soon as you find a toy that costs the same amount or even less than the one you are holding, you get a discount. You take the price of that later toy and subtract it from your toy's price. If you check all the toys that come after yours and find nothing cheaper or equal, you just pay the original price without any discount. This code does exactly that for every single toy by checking them one by one until it finds the best price it can give you. Once it finishes checking for one toy, it hands over the final price and moves on to the next toy in the row until the whole list is finished.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java							TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python		JS	Java				Go	PHP	Rust	TS
	Progiez	C++	Python			Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai					Java
	DimitrisJim								C
	everthis				JS
	fartem						Ruby
	FelixFan1122			C#
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	Shamik07							Dart
	suxrobGM			C#
	trung-hn		Python
	varunu28					Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality