Minimum Levels to Gain More Points - Practice Coding Problems

Minimum Levels to Gain More Points - 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 i-th 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 0-th 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.

Input & Output

Example 1 — Basic Case

$ Input: possible = [1,0,1,0]

› Output: 1

💡 Note: Alice plays level 0 (gains 1 point), Bob plays levels 1,2,3 (loses 1, gains 1, loses 1 = -1 total). Alice: 1, Bob: -1, so Alice wins with just 1 level.

Example 2 — Need More Levels

$ Input: possible = [1,1,1,0]

› Output: 3

💡 Note: If Alice plays 1 level: Alice=1, Bob=2+(-1)=1 (tie). If Alice plays 2 levels: Alice=2, Bob=1+(-1)=0, Alice wins. Actually Alice needs 3 levels to guarantee more points.

Example 3 — Impossible

$ Input: possible = [0,0]

› Output: -1

💡 Note: Both levels are impossible. Both players will lose points, so Alice cannot gain more points than Bob.

Constraints

2 ≤ possible.length ≤ 10⁵
possible[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Binary array [1,0,1,0] representing clearable levels

Split Strategy

Find minimum levels for Alice to beat Bob

Output

Return minimum number of levels (1)

Key Takeaway

🎯 Key Insight: Use prefix sums to efficiently compare Alice's cumulative score against Bob's remaining score

Asked in

G Google 45 a Amazon 38 M Microsoft 32

The key insight is to use prefix sums to efficiently calculate Alice's score vs Bob's remaining score for each possible split point. Best approach uses prefix sum optimization with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n)	O(n)	Pre-calculate prefix sums to avoid recalculating scores repeatedly
Brute Force	O(n²)	O(1)	Try every possible split point and calculate both players' scores

Prefix Sum Optimization — Algorithm Steps

Calculate prefix sum array
For each split point k, use prefix sums
Alice score = prefix[k-1]
Bob score = total_sum - Alice score
Return first k where Alice > Bob

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Array

Calculate cumulative scores

Use Prefix Sums

Alice gets prefix[k-1], Bob gets remaining

Quick Lookup

O(1) score calculation per split

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* possible, int n) {
    // Calculate prefix sums
    int* prefix = (int*)malloc(n * sizeof(int));
    prefix[0] = possible[0] == 1 ? 1 : -1;
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i-1] + (possible[i] == 1 ? 1 : -1);
    }
    
    int totalSum = prefix[n-1];
    
    for (int k = 1; k < n; k++) {
        int aliceScore = prefix[k-1];
        int bobScore = totalSum - aliceScore;
        
        if (aliceScore > bobScore) {
            free(prefix);
            return k;
        }
    }
    
    free(prefix);
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int possible[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            possible[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(possible, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to build prefix sums, then O(n) to check split points

✓ Linear Growth

Space Complexity

O(n)

Extra array to store prefix sums

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~18 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler