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 theminimum number of levels Alice should play to gain more points. If this isnot possible, return -1.

Note that each player must play at least 1 level.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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 <= 10^5
  • possible[i] is either 0 or 1.

Solution

Method 1 – Prefix Sum and Greedy Split

Intuition

We use prefix sums to track Alice’s and Bob’s possible scores for every split. Alice wants the minimum number of levels to play so her score is strictly greater than Bob’s, given both play optimally.

Approach

  1. Compute prefix sums for Alice’s score up to each level.
  2. For each possible split (Alice plays at least 1, Bob at least 1), calculate Alice’s score and Bob’s score.
  3. Alice’s score is the sum of points for the first i levels, Bob’s score is for the rest.
  4. Find the smallest i such that Alice’s score > Bob’s score.
  5. If no such i exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int minimumLevels(vector<int>& possible) {
        int n = possible.size();
        vector<int> prefix(n+1);
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + (possible[i] ? 1 : -1);
        for (int i = 1; i < n; ++i) {
            int alice = prefix[i];
            int bob = prefix[n] - prefix[i];
            if (alice > bob) return i;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func minimumLevels(possible []int) int {
    n := len(possible)
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        if possible[i] == 1 {
            prefix[i+1] = prefix[i] + 1
        } else {
            prefix[i+1] = prefix[i] - 1
        }
    }
    for i := 1; i < n; i++ {
        alice := prefix[i]
        bob := prefix[n] - prefix[i]
        if alice > bob {
            return i
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int minimumLevels(int[] possible) {
        int n = possible.length;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + (possible[i] == 1 ? 1 : -1);
        for (int i = 1; i < n; i++) {
            int alice = prefix[i];
            int bob = prefix[n] - prefix[i];
            if (alice > bob) return i;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun minimumLevels(possible: IntArray): Int {
        val n = possible.size
        val prefix = IntArray(n+1)
        for (i in 0 until n) prefix[i+1] = prefix[i] + if (possible[i] == 1) 1 else -1
        for (i in 1 until n) {
            val alice = prefix[i]
            val bob = prefix[n] - prefix[i]
            if (alice > bob) return i
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def minimum_levels(possible: list[int]) -> int:
    n = len(possible)
    prefix = [0] * (n+1)
    for i in range(n):
        prefix[i+1] = prefix[i] + (1 if possible[i] else -1)
    for i in range(1, n):
        alice = prefix[i]
        bob = prefix[n] - prefix[i]
        if alice > bob:
            return i
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn minimum_levels(possible: Vec<i32>) -> i32 {
        let n = possible.len();
        let mut prefix = vec![0; n+1];
        for i in 0..n {
            prefix[i+1] = prefix[i] + if possible[i] == 1 { 1 } else { -1 };
        }
        for i in 1..n {
            let alice = prefix[i];
            let bob = prefix[n] - prefix[i];
            if alice > bob {
                return i as i32;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    minimumLevels(possible: number[]): number {
        const n = possible.length;
        const prefix = new Array(n+1).fill(0);
        for (let i = 0; i < n; i++) prefix[i+1] = prefix[i] + (possible[i] ? 1 : -1);
        for (let i = 1; i < n; i++) {
            const alice = prefix[i];
            const bob = prefix[n] - prefix[i];
            if (alice > bob) return i;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of possible. We scan the array twice.
  • 🧺 Space complexity: O(n), for the prefix sum array.