Abstract / Summary

Given a list of stone values, remove stones to maximize the score by removing any stone and all stones with the same value, adding their sum to the score each time.

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 69% (80k+ submissions).

Typical patterns to solve this problem:

• Greedy
• Heap (Priority Queue)
• Math

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 solves the problem of maximizing the number of operations that can be performed on three piles of stones. An operation consists of removing one stone from the smallest non-empty pile and one stone from the largest non-empty pile. The algorithm repeatedly applies this rule until fewer than two piles contain stones, at which point no further operation is possible. The final count of performed operations is returned as the result.

Key Steps

Initialization

The function begins by creating a mutable list named state that holds the three input pile sizes. The list is sorted in ascending order so that the smallest pile is at index 0 and the largest pile is at the last index. A variable result is set to zero to accumulate the number of successful operations.

result = 0
state = [a, b, c]
state.sort()

Repeated Operation Loop

A while True loop drives the core logic. Inside each iteration the algorithm decrements the smallest and the largest piles by one, reflecting the removal of a stone from each. The operation counter result is incremented immediately after the decrements.

state[0]  -= 1
state[-1] -= 1
result += 1

Maintaining Order Without Full Sort

After the decrements the relative order of the three values may be disturbed. Rather than invoking a full sort, the code performs a single conditional swap that restores the descending order of the two largest elements. This micro-optimization reduces the overhead of sorting on each iteration.

if state[-1] < state[-2]:
    state[-1], state[-2] = state[-2], state[-1]

Removing Exhausted Piles

When the smallest pile reaches zero, it no longer participates in future operations. A nested while loop removes any leading zero entries from state. If the removal reduces the list length to fewer than two piles, the algorithm terminates and returns the accumulated result.

while state[0] == 0:
    del state[0]
    if len(state) < 2:
        return result

Edge Cases Handled

The code gracefully handles scenarios where one or more input piles start with a size of zero. Because the initial sort places any zero values at the front of state, the first iteration of the outer loop will immediately encounter an empty smallest pile. The inner removal loop will delete those zero entries before any decrement occurs, and the length check will cause an early return with a result of zero, correctly indicating that no operation is possible.

Another edge case occurs when two piles become empty while the third still contains stones. The removal loop continues deleting zero entries until only one non-empty pile remains. The length condition (len(state) < 2) then triggers termination, ensuring that the algorithm does not attempt to access indices that no longer exist.

If all three piles deplete simultaneously, the removal loop will delete each zero entry in turn, and the length condition will be satisfied after the second deletion, returning the total number of operations performed up to that point.

Performance Optimizations

The most notable optimization is the avoidance of a full sort after each operation. By limiting reordering to a single conditional swap of the two largest elements, the algorithm reduces the per-iteration cost from O(log n) sorting to O(1) swapping, where n is the constant size of the list (at most three). This micro-optimization is significant because the loop may execute many times, especially when the input piles are large.

Another subtle optimization is the use of del state[0] to remove exhausted piles. Deleting the first element of a short list is inexpensive, and the subsequent length check prevents unnecessary iterations once the termination condition is met. The inner while loop ensures that multiple consecutive zero piles are removed in a single pass, avoiding repeated checks in the outer loop.

Overall, the algorithm leverages the small, fixed size of the state list to keep each iteration lightweight, resulting in fast execution even for large input values.

Imagine there are three piles of colorful blocks sitting on the floor. Each pile has a different number of blocks in it. The goal is to collect as many points as possible by taking two blocks at a time. To get a point, a block must come from the pile with the most blocks and another block must come from the pile with the fewest blocks.

The code starts by looking at all the blocks and putting the piles in order from smallest to largest so it is easy to find the right ones. Then, a loop begins that repeats the same action over and over. Every time the loop runs, it grabs one block from the biggest pile and one block from the smallest pile to earn a point.

After taking those two blocks, the piles might not be in order anymore because the sizes have changed. The code checks to see if the piles need to be swapped around to keep them in the right order from smallest to biggest. Finally, the code looks to see if any of the piles have run out of blocks. If there are not enough blocks left to keep taking two at a time, the game finishes.

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

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

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