Abstract / Summary

Two players take turns picking numbers from ends of a list trying to maximize their total; determine if the first player can win or tie.

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 56% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Game Theory
• Math
• Recursion

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 determines whether the first player can secure a win (or at least a tie) in a two-player turn-based game where each player alternately picks a number from either end of a list. The algorithm models the game as a zero-sum contest and uses recursion with memoization to evaluate optimal play for both participants.

Core Logic

The method predictTheWinner defines an inner recursive function deeper. This function computes the maximum net score the current player can achieve over the opponent for any sub-array defined by the indices left and right.

@cache
def deeper(left, right):
    if left == right:
        return nums[left]

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

Base Case

When the sub-array collapses to a single element (left == right), the only possible move is to take that element. The function returns its value, representing the net advantage for the player whose turn it is.

if left == right:
    return nums[left]

Evaluating Choices

Two scenarios are examined:

• Selecting the leftmost element (nums[left]). The opponent then faces the sub-array [left+1, right]. The net result for the current player is the chosen value minus the opponent’s optimal response, expressed as nums[left] - deeper(left + 1, right).

• Selecting the rightmost element (nums[right]). The opponent subsequently confronts [left, right-1]. The net result is nums[right] - deeper(left, right - 1).

The function returns the larger of these two net results, reflecting optimal play.

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

Final Decision

After evaluating the entire array (deeper(0, len(nums) - 1)), the method checks whether the computed net advantage is non-negative. A non-negative value indicates that the first player can at least tie, which satisfies the problem’s winning condition.

return deeper(0, len(nums) - 1) >= 0

Edge Cases Handled

• Single-element list - The base case immediately returns the sole value, and the final comparison yields True because the first player obtains the only number.

• All elements equal - Both choices produce identical net results at each recursion level, leading to a net advantage of zero for the first player, which satisfies the >= 0 condition.

• Presence of negative numbers - The subtraction of the opponent’s optimal response correctly propagates negative contributions, ensuring that the algorithm still evaluates the true net advantage.

• Maximum length constraints - The recursion depth never exceeds the length of the list, preventing stack overflow for typical input sizes.

Performance Optimizations

The most significant optimization is the use of the @cache decorator (from functools). By caching the results of deeper(left, right) for each distinct pair of indices, the algorithm avoids recomputing identical sub-problems. This transforms an otherwise exponential exploration of game states into a polynomial number of evaluations, as each pair (left, right) is processed only once.

The memoization leverages Python’s built-in dictionary for constant-time lookups, which is faster than manual caching structures. Additionally, the recursion operates directly on index boundaries without creating new list slices, thereby minimizing memory overhead and avoiding unnecessary copying of data.

Overall, the combination of a concise recursive formulation and built-in caching yields an efficient solution that scales well with the size of the input list.

Imagine there is a long row of yummy cookies waiting on a table. Two friends want to share them, but each friend wants to get as many cookies for themselves as possible. To play this game, each friend can only take a cookie from either the very far left side or the very far right side of the row. They take turns picking a cookie one by one until all of them are gone.

The code works by looking ahead at all the possible ways the game could play out. It acts like a very clever bird flying high above the table to see every move from the start to the end. It thinks about what would happen if a player picks the cookie on the left versus what would happen if they pick the cookie on the right.

Whenever it figures out the result for a certain set of cookies, it writes that result down in a little notebook. If it sees the same set of cookies again, it just checks its notebook instead of thinking about it all over again. This helps it know exactly who will end up with more cookies by the time the table is empty. By checking every single choice, the code decides if the person who goes first can win the game.

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++				Java
	leetcode.ca	C++		Rust	Python	Java			Go	TS
	LeetcodeHelp	C++			Python	Java
	MemoryLimitExceeded	C++			Python
	Progiez	C++			Python	Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	fengvyi	C++
	JoshCrozier		JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007				Python
	lzl124631x	C++
	ruoru			Rust
	suxrobGM						C#
	vli02							C
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
vli02	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