Abstract / Summary

Find the fewest levels to play so the total points earned exceed a given target.

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 41% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Prefix Sum

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 minimumLevels method determines the earliest level at which Alice’s cumulative advantage over Bob becomes positive, given a list that encodes the outcome of each level for Bob. The algorithm treats the list as a sequence of binary results, where 1 indicates a win for Bob and 0 a loss. By translating these outcomes into a symmetric score system and updating two running totals, the method can stop as soon as Alice overtakes Bob, returning the number of levels required. If Alice never gains the lead, the function returns -1.

Key Steps

Counting wins and losses

size = len(possible)
won  = possible.count(1)
lost = size - won

The code first records the total number of levels and separates the count of winning entries (won) from losing entries (lost). This information is used to initialize the players’ scores.

Initial score assignment

alice = 0
bob   = won - lost

Alice starts with a neutral score of zero. Bob’s initial score reflects the net advantage he would have if he played every level: each win contributes +1 and each loss -1, so the difference won - lost captures his total lead before any level is processed.

Ensuring the last level belongs to Bob

possible.pop()

The problem statement requires that Bob must participate in the final level. By removing the last element from the list, the algorithm guarantees that the subsequent loop processes only the earlier levels, leaving the final level implicitly assigned to Bob.

Iterating through the remaining levels

for i, p in enumerate(possible, 1):
    score  = 2 * p - 1   # convert [0, 1] to [-1, +1]
    alice += score
    bob   -= score
    if alice > bob:
        return i

The loop walks through each remaining level, converting the binary outcome p into a symmetric score (-1 for a loss, +1 for a win). Alice’s total is increased by this score, while Bob’s total is decreased by the same amount, reflecting the opposite effect of the level on the two players. After each update, the method checks whether Alice’s cumulative score exceeds Bob’s; if so, the current index i (1-based) is returned as the minimal number of levels needed for Alice to lead.

Default return when Alice never leads

return -1

If the loop completes without Alice ever surpassing Bob, the function signals failure to achieve a lead by returning -1.

Edge Cases Handled

When the input list contains only a single element, the pop operation empties the list, causing the loop to be skipped entirely. In this situation the method directly proceeds to the final return -1, correctly indicating that Alice cannot obtain a lead because there are no earlier levels to influence the score.

If the initial net advantage for Bob (won - lost) is already non-positive, Alice starts ahead or tied. The first iteration of the loop will immediately evaluate the condition alice > bob. Because Alice’s score begins at zero and Bob’s may be zero or negative, the early return can occur after processing just one level, handling the scenario where Alice needs only the first level to secure the lead.

When all entries are wins (possible consists solely of 1s), the conversion yields a score of +1 for each level. Alice’s total grows positively while Bob’s total declines, guaranteeing that the condition alice > bob will be satisfied at some point before the list is exhausted, and the method will return the appropriate index.

Conversely, if all entries are losses (0s), each iteration adds -1 to Alice and +1 to Bob, making it impossible for Alice to overtake Bob. The loop runs to completion and the method returns -1, correctly reflecting that Alice can never lead under these circumstances.

Performance Optimizations

The implementation leverages Python’s built-in list.count to obtain the number of wins in a single pass, avoiding manual iteration for that purpose. By computing Bob’s initial net advantage directly from the win/loss counts, the algorithm eliminates the need for a separate accumulation step.

The conversion from binary outcomes to a symmetric score (2 * p - 1) is performed with simple arithmetic, avoiding conditional branches that could introduce branching penalties. Updating both players’ scores in the same iteration keeps the algorithm’s state tightly localized, which benefits CPU cache utilization.

The early-exit condition (if alice > bob: return i) allows the method to stop processing as soon as the required lead is achieved, potentially reducing the number of iterations dramatically for favorable inputs. The in-place pop operation removes the last element without allocating a new list, preserving memory usage and avoiding unnecessary copying.

Imagine a long line of game levels. Each level is either a one, which means winning a point, or a zero, which means losing a point. Alice and Bob want to split these levels between them. They take turns going through the list from the beginning to the end, but they must keep going until everyone has played at least one level.

First, the computer counts how many total points Bob would have if he played every single level. It sees total wins and total losses to figure out that starting score.

Then, the code starts walking through the list of levels. Every time it looks at a level, it pretends Alice is playing it. If she gets a win, she gains a point, but Bob loses that same point because he is no longer playing that level. If she gets a loss, she loses a point, and Bob gains that point instead.

The loop keeps checking after every level to see if Alice has a higher score than Bob. As soon as Alice has more points than Bob, the process stops. This tells everyone exactly how many levels Alice needs to play to be in the lead. If she goes through all the allowed levels and still does not have a higher score, the game concludes that it is not possible for her to win.

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	Java	C++		Python	TS
	WalkCCC	Java	C++		Python
	leetcode.ca	Java	C++	Go	Python	TS
	Progiez	Java	C++		Python
github	charles-wangkai	Java
	fsq		C++
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
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