Abstract / Summary

You must buy all candies paying full price for the most expensive ones and get discounts on every two cheapest ones bought together.

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 72% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Sorting

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 Solution class implements a method minimumCost that computes the smallest possible total price when purchasing a collection of items whose individual costs are given in the list cost. The pricing rule is that for every group of three items, the cheapest one is obtained for free. By arranging the purchases to maximize the value of the free items, the algorithm yields the minimal total expense.

Core Logic

The algorithm proceeds in three distinct phases: sorting the input, iterating through the sorted values while tracking group membership, and accumulating the payable amount.

Sorting the Costs

for c in sorted(cost, reverse = True):

The sorted function is invoked with reverse = True, producing a new list ordered from the highest cost to the lowest. Placing the most expensive items first ensures that when groups of three are formed, the free item will be the smallest within each group, thereby maximizing the discount.

Group Counter

three  = 1

A simple integer variable named three acts as a group counter. It starts at 1 and is incremented for each processed item until it reaches 3. When the counter hits 3, the algorithm knows that the current item should be treated as the free one.

Conditional Accumulation

if three < 3:
    result += c
    three  += 1
else:
    three   = 1

If the counter is less than 3, the current cost c is added to the running total result, and the counter is advanced. When the counter equals 3, the else branch executes: the counter is reset to 1 and the cost is deliberately omitted from result. This omission implements the “free item” rule without needing an explicit subtraction.

Final Return

return result

After all costs have been processed, the accumulated result holds the minimal payable amount and is returned to the caller.

Edge-Case Handling

The method gracefully handles several boundary conditions without additional code paths.

When the input list cost is empty, the for loop never iterates, leaving result at its initial value of 0. Consequently, the function returns 0, which correctly represents the cost of buying nothing.

If the list contains one or two elements, the counter never reaches 3. Both items are added to result, reflecting that no free item can be granted when fewer than three purchases are made.

For lists whose length is an exact multiple of three, every third item is omitted from the total. The counter resets after each omission, ensuring that the pattern repeats consistently throughout the entire list.

When the length leaves a remainder of one or two after division by three, the remaining one or two most expensive items are still added to result. The counter’s reset logic guarantees that only complete groups of three trigger the free-item condition.

Performance Optimizations

The implementation leverages a few subtle choices that contribute to efficient execution.

Using the built-in sorted function with the reverse flag takes advantage of the highly optimized Timsort algorithm, which performs well on partially ordered data and minimizes memory overhead by sorting in place when possible.

The group-tracking mechanism relies on a plain integer increment and a comparison rather than a modulo operation (i % 3). This avoids the cost of division and remainder calculation on each iteration, yielding a tighter inner loop.

No auxiliary data structures such as additional lists or sets are created during iteration. The algorithm maintains only three scalar variables (result, three, and the loop variable c), keeping the memory footprint minimal.

By processing the sorted list in a single pass, the method achieves a linear traversal after the initial sort, ensuring that the dominant work is confined to the sorting step while the accumulation phase remains lightweight.

Imagine there is a big pile of colorful candies in front of a candy store. The shop has a special deal where if you pick two candies to buy, you get a third one for free. To make sure the shopkeeper packs them correctly, the candies are first lined up from the most expensive one to the cheapest one.

The program starts by looking at the very first candy, which is the most expensive, and puts it in a basket. Then it grabs the next most expensive one and puts that one in the basket too. Since two candies are now waiting to be paid for, the third one is a free gift. Because that third candy is free, the program skips it and stops counting it toward the total price.

After that, the program starts the pattern all over again. It takes the next candy as if it were the start of a new group of three. It keeps doing this, picking two candies to buy and getting one for free, until there are no candies left. By the end, the basket is full of all the candies that need to be paid for, and the total cost for those candies is ready.

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

Time: loglinear
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++	Java		Python			TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python		Go	TS
	Progiez	C++	Java		Python
github	black-shadows	C++
	charles-wangkai		Java
	fsq	C++
	JoshCrozier					JS
	lkwq007				Python
	shreymehul			C#
	suxrobGM			C#
	varunu28		Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
suxrobGM	C#
varunu28	Java
withaarzoo	C++

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