Abstract / Summary

Two players take turns picking stones from piles and the first with an odd total wins.

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 74% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Game Theory
• 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 classic two-player “Stone Game” where two participants alternately take a pile of stones from either end of a line. The goal is to determine whether the first player can secure a total strictly greater than the second player when both play optimally. The solution employs a recursive depth-first search with memoization to evaluate the optimal score difference for any sub-array of piles.

Core Logic

The heart of the algorithm is the nested function deeper. It receives two indices, left and right, that delimit the current segment of the piles list under consideration. The function returns the maximum net advantage the current player can achieve over the opponent for that segment.

@cache
def deeper(left, right):
    if left > right:
        return 0

    l = piles[left] - deeper(left + 1, right)
    r = piles[right] - deeper(left, right - 1)
    return max(l, r)

The base case if left > right: return 0 handles the situation where no piles remain, yielding a neutral score difference. The two recursive branches correspond to the two legal moves: taking the leftmost pile (l) or the rightmost pile (r). After a player takes a pile, the opponent becomes the active player for the reduced segment, which is why the recursive call is subtracted from the value of the taken pile. The max selects the move that maximizes the current player’s advantage.

The outer method simply initiates the recursion for the full range of piles.

return deeper(0, len(piles) - 1)

Because the function returns the net advantage, a positive result indicates that the first player can outscore the second player. The method therefore returns True whenever the computed advantage is positive, which aligns with the problem’s requirement.

Edge Cases Handled

When the input list contains a single pile, the recursion quickly reaches the base case after one step. The left > right guard ensures that the function does not attempt to access out-of-range indices. An empty list, though not a typical input for the problem, would also be safely handled: the initial call would have right = -1, causing the base case to trigger immediately and return 0, leading the outer method to return False.

The implementation also gracefully manages cases where all piles have equal values. The subtraction of the opponent’s optimal response guarantees that the algorithm correctly evaluates the parity of the total sum, yielding the appropriate boolean outcome.

Performance Optimizations

The most significant optimization is the use of the @cache decorator from Python’s functools. This memoization caches the result of each distinct (left, right) pair, preventing exponential recomputation of overlapping subproblems. As a result, each sub-segment of the array is evaluated at most once, turning what would be a naïve exponential recursion into a polynomial-time solution.

Another subtle optimization lies in the direct arithmetic expression piles[left] - deeper(left + 1, right). By computing the net advantage in a single step, the code avoids the need for auxiliary data structures or additional temporary variables, keeping the memory footprint low and the execution path tight.

The recursion depth is bounded by the number of piles, which aligns with the natural stack depth for this problem. Python’s recursion limit is typically sufficient for the input sizes expected in competitive programming contexts, and the memoization ensures that the call stack does not explode due to repeated subcalls.

Flow Summary

The algorithm begins by invoking deeper on the full interval. Inside deeper, the base case checks for an empty interval. If piles remain, the function evaluates the two possible moves, each time subtracting the opponent’s optimal response obtained via a recursive call. The max function selects the better of the two outcomes, and the result propagates back up the call stack. Finally, the outer method interprets the returned net advantage as a boolean indicating whether the first player can guarantee a win.

Imagine there is a long row of shiny stones sitting on the ground, and two friends are taking turns picking them up. Each stone has a different size, and everyone wants to collect the biggest pile possible.

The code acts like a very smart thinker that looks at the row of stones. It knows that whenever it is someone's turn, they can only pick a stone from the very left end or the very right end of the line. Because the thinker wants to know who wins, it imagines playing the game over and over again in its head.

It starts by looking at the whole row. If it takes the stone from the left, it then thinks about what the other player would do with what is left. Then, it does the same thing for the stone on the right. By comparing these two choices, the thinker figures out the best move to make so that the person who starts the game ends up with more stones than the other player.

The little puzzle inside the code remembers every single position it has already thought about so it does not have to do the same work twice. It keeps looking at smaller and smaller parts of the row until all the stones are gone. By the time it finishes, it knows exactly if the person who starts the game will have the most stones.

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++	Java					Python	TS
	WalkCCC	C++	Java					Python
	leetcode.ca	C++	Java		Rust		Go	Python	TS
	LeetcodeHelp	C++	Java					Python
	Progiez	C++	Java					Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	FelixFan1122		Java
	gouthampradhan		Java
	halfrost						Go
	JoshCrozier					JS
	keineahnung2345	C++
	MacJim	C++
	ruoru				Rust
	suxrobGM			C#
	wisdompeak	C++
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
FelixFan1122	Java
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
MacJim	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	C++
withaarzoo	C++
zfang399	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