You are given a binary array possible of length n.
Alice and Bob are playing a game that consists of n levels. Some of the levels in the game are impossible to clear while others can always be cleared. In particular, if possible[i] == 0, then the ith level is impossible to clear for both the players. A player gains 1 point on clearing a level and loses 1 point if the player fails to clear it.
At the start of the game, Alice will play some levels in the given order starting from the 0th level, after which Bob will play for the rest of the levels.
Alice wants to know the minimum number of levels she should play to gain more points than Bob, if both players play optimally to maximize their points.
Return the minimum number of levels Alice should play to gain more points. If this is not possible, return -1.
Note that each player must play at least 1 level.
Example 1:
Input: possible = [1,0,1,0]
Output: 1
Explanation:
Let's look at all the levels that Alice can play up to:
Alice must play a minimum of 1 level to gain more points.
Example 2:
Input: possible = [1,1,1,1,1]
Output: 3
Explanation:
Let's look at all the levels that Alice can play up to:
Alice must play a minimum of 3 levels to gain more points.
Example 3:
Input: possible = [0,0]
Output: -1
Explanation:
The only possible way is for both players to play 1 level each. Alice plays level 0 and loses 1 point. Bob plays level 1 and loses 1 point. As both players have equal points, Alice can't gain more points than Bob.
Constraints:
2 <= n == possible.length <= 105possible[i] is either 0 or 1.Problem Overview: You are given an array where each level either gives +1 point or -1 point depending on whether it is winnable. Alice plays the first k levels and Bob plays the remaining levels. The task is to find the minimum k such that Alice’s total score is strictly greater than Bob’s, while ensuring Bob still plays at least one level.
Approach 1: Prefix Sum and Greedy Selection (O(n) time, O(1) space)
Convert the game outcome into a score representation: treat 1 as +1 point and 0 as -1. First compute the total score of all levels. Then iterate from left to right while maintaining a running prefix score for Alice. Bob’s score at any split point can be computed as totalScore - prefixScore. The earliest index where prefixScore > totalScore - prefixScore satisfies the requirement. Return that position as the minimum number of levels Alice should play, ensuring the split happens before the last element so Bob has at least one level. This works because each iteration updates Alice’s score incrementally and compares it with Bob’s remaining score. The approach only requires a single pass over the array with a running prefix sum, making it the most efficient solution.
Approach 2: Binary Search on Points Difference (O(n log n) time, O(n) space)
Precompute a prefix sum array where each entry stores the cumulative score up to that level. With prefix sums available, Alice’s score for the first k levels is prefix[k] and Bob’s score becomes prefix[n] - prefix[k]. Instead of scanning linearly, perform a binary search on the split point k. For each candidate midpoint, calculate Alice’s and Bob’s scores using constant-time prefix queries. If Alice’s score is already greater, move the search left to find a smaller valid split; otherwise move right. This approach is slightly heavier because it builds a prefix array and performs multiple checks, but it demonstrates how prefix sums enable fast range queries that pair well with binary search.
Recommended for interviews: The Prefix Sum + Greedy scan is the expected solution. It runs in linear time, uses constant extra space, and clearly demonstrates understanding of prefix sums and score comparisons. Showing the brute reasoning—compute both players’ scores and check the earliest valid split—proves correctness, while the optimized single-pass implementation highlights strong algorithmic thinking.
This approach involves calculating the accumulated points that Alice and Bob will have if Alice stops playing at different levels and Bob starts playing right afterwards. We maintain prefix sums to calculate the points each player has efficiently. The idea is to advance through the levels until Alice's points exceed Bob's points.
This code calculates the minimum number of levels Alice needs to play to have more points than Bob. It uses a simple loop to count how many levels Alice should play iteratively, updating the scores of Alice and Bob based on the levels that Alice has chosen to play.
Time Complexity: O(n), where n is the length of the array `possible`.
Space Complexity: O(1), since we are using only constant extra space.
This approach employs binary search to determine the minimum number of levels Alice must play in order to have a greater point score than Bob. We compute the point differential at each possible division of the levels.
This C program uses a helper function to check if Alice can have more points than Bob at a given splitting point `mid`, using binary search to narrow down the minimum split where this condition holds true.
Time Complexity: O(n log n), due to binary search over the possible split points, each check costing O(n).
Space Complexity: O(1), using constant extra space.
First, we calculate the sum of the scores that both players can get, denoted as s.
Then, we enumerate the number of levels that player 1 can complete, denoted as i, in ascending order. We calculate the sum of the scores that player 1 gets, denoted as t. If t > s - t, then the number of levels that player 1 needs to complete is i.
If we have enumerated the first n - 1 levels and have not found a satisfying i, then we return -1.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix Sum and Greedy Selection | Time Complexity: O(n), where n is the length of the array `possible`. |
| Binary Search on Points Difference | Time Complexity: O(n log n), due to binary search over the possible split points, each check costing O(n). |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum and Greedy Selection | O(n) | O(1) | Best general solution. Single pass with running score comparison. |
| Binary Search on Points Difference | O(n log n) | O(n) | When prefix sums are already precomputed or when demonstrating binary search over split positions. |
3096. Minimum Levels to Gain More Points | Prefix Sums | Arrays • Aryan Mittal • 1,139 views views
Watch 7 more video solutions →Practice Minimum Levels to Gain More Points with our built-in code editor and test cases.
Practice on FleetCode