Minimum Levels to Gain More Points solution and explanation
IBM
6 more videos on this problem
3096. Minimum Levels to Gain More Points | Prefix Sums | ArraysAryan Mittal · 7:42 · 1K views
3096. Minimum Levels to Gain More Points (Leetcode Medium)Programming Live with Larry · 12:33 · 198 views
Leetcode 3096: Minimum Levels to Gain More Points - PythonAlgorithms Casts · 11:29 · 121 views
3096. Minimum Levels to Gain More Points || Leetcode biweekly contest 127 || HindiAshish Kumar · 6:42 · 82 views
3096. Minimum Levels to Gain More Points | Prefix SumTech Courses · 6:56 · 61 views
3096. Minimum Levels to Gain More Points || Prefix Suffix Sum || O(N) TC || Leetcode Biweekly🔥🔥Code With Anubhav · 25:51 · 27 views
📸𝑩𝒊𝒘𝒆𝒆𝒌𝒍𝒚 𝑪𝒐𝒏𝒕𝒆𝒔𝒕 𝟭𝟮𝟳 𝑷𝒓𝒐𝒃𝒍𝒆𝒎 𝟮: 𝟯𝟬𝟵𝟲. 𝑴𝒊𝒏𝒊𝒎𝒖𝒎 𝑳𝒆𝒗𝒆𝒍𝒔 𝒕𝒐 𝑮𝒂𝒊𝒏 𝑴𝒐𝒓𝒆 𝑷𝒐𝒊𝒏𝒕𝒔 || 𝑳𝒆𝒆𝒕𝒄𝒐𝒅𝒆Achyuth Chowdary · 7:58 · 24 views
The problem
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:
- If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has -1 + 1 - 1 = -1 point.
- If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 1 - 1 = 0 points, while Bob has 1 - 1 = 0 points.
- If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 1 - 1 + 1 = 1 point, while Bob has -1 point.
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:
- If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has 4 points.
- If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 2 points, while Bob has 3 points.
- If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 3 points, while Bob has 2 points.
- If Alice plays till level 3 and Bob plays the rest of the levels, Alice has 4 points, while Bob has 1 point.
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 either0or1.
Approach overview
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.
Approach 1: Prefix Sum and Greedy Selection
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.
def min_levels_to_gain_more_points(possible):
n = len(possible)
alice_points = 0
total_clearable = sum(possible)
for i in range(n):
alice_points += possible[i]
bob_points = total_clearable - alice_points
if alice_points > bob_points and i + 1 >= 1 and n - i - 1 >= 1:
return i + 1
return -1
possible = [1, 0, 1, 0]
print(min_levels_to_gain_more_points(possible))public class GamePoints {
public static int minLevelsToGainMorePoints(int[] possible) {
int n = possible.length;
int alicePoints = 0, totalClearable = 0;
for (int val : possible) {
if (val == 1) totalClearable++;
}
for (int i = 0; i < n; ++i) {
alicePoints += possible[i];
int bobPoints = totalClearable - alicePoints;
if (alicePoints > bobPoints && i + 1 >= 1 && n - i - 1 >= 1) {
return i + 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] possible = {1, 0, 1, 0};
System.out.println(minLevelsToGainMorePoints(possible));
}
}#include <iostream>
#include <vector>
using namespace std;
int minLevelsToGainMorePoints(vector<int>& possible) {
int n = possible.size();
int alicePoints = 0, bobPoints, totalClearable = 0;
for (int val : possible) {
if (val == 1) totalClearable++;
}
for (int i = 0; i < n; ++i) {
alicePoints += possible[i];
bobPoints = totalClearable - alicePoints;
if (alicePoints > bobPoints && i + 1 >= 1 && n - i - 1 >= 1) {
return i + 1;
}
}
return -1;
}
int main() {
vector<int> possible = {1, 0, 1, 0};
cout << minLevelsToGainMorePoints(possible) << endl;
return 0;
}function minLevelsToGainMorePoints(possible) {
const n = possible.length;
let alicePoints = 0;
let totalClearable = possible.reduce((a, b) => a + b, 0);
for (let i = 0; i < n; i++) {
alicePoints += possible[i];
let bobPoints = totalClearable - alicePoints;
if (alicePoints > bobPoints && i + 1 >= 1 && n - i - 1 >= 1) {
return i + 1;
}
}
return -1;
}
console.log(minLevelsToGainMorePoints([1, 0, 1, 0]));#include <stdio.h>
int minLevelsToGainMorePoints(int* possible, int n) {
int alicePoints = 0, bobPoints = 0, totalClearable = 0;
for (int i = 0; i < n; ++i) {
if (possible[i] == 1) {
totalClearable += 1;
}
}
for (int i = 0; i < n; ++i) {
if (possible[i] == 1) {
alicePoints += 1;
}
bobPoints = totalClearable - alicePoints;
if (alicePoints > bobPoints && i + 1 >= 1 && n - i - 1 >= 1) {
return i + 1;
}
}
return -1;
}
int main() {
int possible[] = {1, 0, 1, 0};
int n = sizeof(possible) / sizeof(possible[0]);
int result = minLevelsToGainMorePoints(possible, n);
printf("%d\n", result);
return 0;
}using System;
class GamePoints {
public static int MinLevelsToGainMorePoints(int[] possible) {
int n = possible.Length;
int alicePoints = 0, totalClearable = 0;
foreach (var val in possible) {
if (val == 1) totalClearable++;
}
for (int i = 0; i < n; i++) {
alicePoints += possible[i];
int bobPoints = totalClearable - alicePoints;
if (alicePoints > bobPoints && i + 1 >= 1 && n - i - 1 >= 1) {
return i + 1;
}
}
return -1;
}
static void Main(string[] args) {
int[] possible = {1, 0, 1, 0};
Console.WriteLine(MinLevelsToGainMorePoints(possible));
}
}This Python function tracks Alice's score and calculates the leftover levels Bob can clear, comparing their scores at each step until Alice's surpasses Bob's.
Time Complexity: O(n), where n is the length of the array `possible`.
Space Complexity: O(1), only using fixed auxiliary space.
Approach 2: Binary Search on Points Difference
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.
def can_alice_have_more_points(possible, mid):
alice_points = sum(possible[:mid])
total_clearable = sum(possible)
bob_points = total_clearable - alice_points
return alice_points > bob_points
def min_levels_binary_search(possible):
n = len(possible)
left, right = 1, n - 1
result = -1
while left <= right:
mid = (left + right) // 2
if can_alice_have_more_points(possible, mid):
result = mid
right = mid - 1
else:
left = mid + 1
return result
possible = [1, 0, 1, 0]
print(min_levels_binary_search(possible))import java.util.*;
public class GamePoints {
private static boolean canAliceHaveMorePoints(int[] possible, int mid) {
int alicePoints = 0, totalClearable = 0;
for (int val : possible) {
if (val == 1) totalClearable++;
}
for (int i = 0; i < mid; ++i) {
alicePoints += possible[i];
}
int bobPoints = totalClearable - alicePoints;
return alicePoints > bobPoints;
}
public static int minLevelsBinarySearch(int[] possible) {
int n = possible.length;
int left = 1, right = n - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAliceHaveMorePoints(possible, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
public static void main(String[] args) {
int[] possible = {1, 0, 1, 0};
System.out.println(minLevelsBinarySearch(possible));
}
}#include <iostream>
#include <vector>
using namespace std;
bool canAliceHaveMorePoints(const vector<int>& possible, int mid) {
int alicePoints = 0, totalClearable = 0;
for (int val : possible) {
if (val == 1) totalClearable++;
}
for (int i = 0; i < mid; ++i) {
alicePoints += possible[i];
}
int bobPoints = totalClearable - alicePoints;
return alicePoints > bobPoints;
}
int minLevelsBinarySearch(const vector<int>& possible) {
int n = possible.size();
int left = 1, right = n - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAliceHaveMorePoints(possible, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
int main() {
vector<int> possible = {1, 0, 1, 0};
cout << minLevelsBinarySearch(possible) << endl;
return 0;
}function canAliceHaveMorePoints(possible, mid) {
const alicePoints = possible.slice(0, mid).reduce((a, b) => a + b, 0);
const totalClearable = possible.reduce((a, b) => a + b, 0);
const bobPoints = totalClearable - alicePoints;
return alicePoints > bobPoints;
}
function minLevelsBinarySearch(possible) {
const n = possible.length;
let left = 1, right = n - 1, result = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (canAliceHaveMorePoints(possible, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
console.log(minLevelsBinarySearch([1, 0, 1, 0]));#include <stdio.h>
int canAliceHaveMorePoints(int* possible, int n, int mid) {
int alicePoints = 0, bobPoints = 0, totalClearable = 0;
for (int i = 0; i < n; ++i) {
if (possible[i] == 1) {
totalClearable++;
}
}
int i;
for (i = 0; i < mid; ++i) {
alicePoints += possible[i];
}
bobPoints = totalClearable - alicePoints;
return alicePoints > bobPoints;
}
int minLevelsBinarySearch(int* possible, int n) {
int left = 1, right = n - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAliceHaveMorePoints(possible, n, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
int main() {
int possible[] = {1, 0, 1, 0};
int n = sizeof(possible) / sizeof(possible[0]);
printf("%d\n", minLevelsBinarySearch(possible, n));
return 0;
}using System;
class GamePoints {
private static bool CanAliceHaveMorePoints(int[] possible, int mid) {
int alicePoints = 0, totalClearable = 0;
foreach (var val in possible) {
if (val == 1) totalClearable++;
}
for (int i = 0; i < mid; ++i) {
alicePoints += possible[i];
}
int bobPoints = totalClearable - alicePoints;
return alicePoints > bobPoints;
}
public static int MinLevelsBinarySearch(int[] possible) {
int n = possible.Length;
int left = 1, right = n - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (CanAliceHaveMorePoints(possible, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
static void Main(string[] args) {
int[] possible = {1, 0, 1, 0};
Console.WriteLine(MinLevelsBinarySearch(possible));
}
}This Python code leverages a binary search to efficiently pinpoint the lowest levels count Alice needs to achieve higher points than Bob. By calculating the point differential, it ensures quick convergence to the minimum requisite levels.
Time Complexity: O(n log n), leveraging binary search to check potential player split points.
Space Complexity: O(1), requiring only fixed space.
Approach 3: Enumeration
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).
function minimumLevels(possible: number[]): number {
const s = possible.reduce((acc, x) => acc + (x === 0 ? -1 : 1), 0);
let t = 0;
for (let i = 1; i < possible.length; ++i) {
t += possible[i - 1] === 0 ? -1 : 1;
if (t > s - t) {
return i;
}
}
return -1;
}func minimumLevels(possible []int) int {
s := 0
for _, x := range possible {
if x == 0 {
x = -1
}
s += x
}
t := 0
for i, x := range possible[:len(possible)-1] {
if x == 0 {
x = -1
}
t += x
if t > s-t {
return i + 1
}
}
return -1
}Complexity comparison
| 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), leveraging binary search to check potential player split points. |
| Enumeration | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Levels to Gain More Points easy or hard?
The problem is rated Medium because it requires recognizing that the game can be transformed into a prefix sum comparison problem. Once the scoring is converted to +1 and -1 values, the optimal solution becomes a straightforward linear scan.
Minimum Levels to Gain More Points Python/Java solution
Most implementations convert the input into +1 and -1 scores, compute the total score, and scan from left to right updating a running prefix sum. The condition prefix > total - prefix determines the earliest split. The same logic works in Python, Java, C++, C#, and JavaScript with O(n) time complexity.
How to solve Minimum Levels to Gain More Points in O(n)?
Convert the input into scores where 1 becomes +1 and 0 becomes -1. Compute the total score of all levels, then iterate through the array while accumulating a prefix score for Alice. At each index check whether prefixScore > totalScore - prefixScore and ensure Bob still has at least one level. The first index satisfying this condition is the answer.
What is the best approach for Minimum Levels to Gain More Points?
The optimal approach uses a prefix sum with a greedy scan. Convert each level to +1 or -1 points, compute the total score, then iterate while maintaining Alice's running score. The first index where Alice's score becomes greater than Bob's remaining score gives the minimum valid split. This runs in O(n) time and O(1) extra space.
Is Minimum Levels to Gain More Points asked at Google/Amazon/Meta?
Prefix sum and greedy split problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers often use them to test understanding of prefix sums, score comparisons, and efficient single-pass array processing.
What data structure is used in Minimum Levels to Gain More Points?
The core technique relies on arrays and prefix sums. A running prefix sum tracks Alice's accumulated score, while the remaining score for Bob is derived from the total. Some variations also store prefix sums in an array to enable constant-time range queries.
What is the time complexity of Minimum Levels to Gain More Points?
The optimal solution runs in O(n) time because the array is scanned once while maintaining a running prefix score. Space complexity is O(1) if the prefix sum is tracked using a single variable, or O(n) if a full prefix array is stored.