# Minimum Levels to Gain More Points
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-levels-to-gain-more-points)
Canonical: https://scaleengineer.com/dsa/problems/minimum-levels-to-gain-more-points
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## 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 <= 105`
* `possible[i]` is either `0` or `1`.

# Approaches
## Brute Force Simulation
This approach directly simulates the game for every possible split point. For each number of levels `k` that Alice could play (from 1 to n-1), we calculate her score and Bob's score from scratch by iterating through their respective level ranges and then compare them.
**Time:** O(n^2) - The outer loop runs `n-1` times. For each iteration, we perform two inner loops that, combined, iterate through all `n` elements to calculate the scores. This results in a quadratic time complexity. · **Space:** O(1) - We only use a constant amount of extra space for variables like `aliceScore`, `bobScore`, and loop counters.
**Pros:** Simple to understand and implement as it directly translates the problem description into code.; It is guaranteed to be correct, as it exhaustively checks all possibilities.
**Cons:** Highly inefficient due to repeated calculations for scores in each iteration.; The time complexity of O(n^2) will result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.
### Explanation
The brute-force method involves checking every possible scenario. Alice must play at least one level, and Bob must also play at least one. This means Alice can play `k` levels, where `k` ranges from `1` to `n-1`.

For each potential value of `k`, we perform two separate calculations:
1.  **Alice's Score**: We loop from level `0` to `k-1`. For each level `i`, if `possible[i]` is `1`, we add 1 to `aliceScore`; otherwise, we subtract 1.
2.  **Bob's Score**: We loop from level `k` to `n-1`. Similarly, for each level `j`, if `possible[j]` is `1`, we add 1 to `bobScore`; otherwise, we subtract 1.

After calculating both scores, we check if `aliceScore > bobScore`. Since our outer loop for `k` starts from `1` and goes up, the very first time this condition is met, we have found the minimum `k`. We can immediately return this value. If the loop finishes and we haven't found any such `k`, it's impossible for Alice to win, so we return `-1`.

```java
class Solution {
    public int minimumLevels(int[] possible) {
        int n = possible.length;
        // k is the number of levels Alice plays.
        // Alice must play at least 1 level, and Bob must play at least 1.
        // So, k can range from 1 to n-1.
        for (int k = 1; k < n; k++) {
            int aliceScore = 0;
            // Calculate Alice's score for levels 0 to k-1
            for (int i = 0; i < k; i++) {
                if (possible[i] == 1) {
                    aliceScore++;
                } else {
                    aliceScore--;
                }
            }

            int bobScore = 0;
            // Calculate Bob's score for levels k to n-1
            for (int i = k; i < n; i++) {
                if (possible[i] == 1) {
                    bobScore++;
                } else {
                    bobScore--;
                }
            }

            if (aliceScore > bobScore) {
                return k;
            }
        }
        return -1;
    }
}
```
### Algorithm
*   Iterate through all possible numbers of levels `k` that Alice can play, from `1` to `n-1`.
*   For each `k`, initialize `aliceScore` and `bobScore` to `0`.
*   Calculate `aliceScore` by iterating from level `0` to `k-1`. Add `1` for a possible level (`1`) and subtract `1` for an impossible level (`0`).
*   Calculate `bobScore` by iterating from level `k` to `n-1` using the same scoring logic.
*   If `aliceScore` is strictly greater than `bobScore`, it means we have found a valid split. Since we are iterating `k` in increasing order, this is the minimum number of levels. Return `k`.
*   If the loop completes without finding such a `k`, return `-1`.

## Single Pass with Prefix Sum
This approach optimizes the calculation by observing the relationship between Alice's score, Bob's score, and the total score of all levels. By calculating the total score once at the beginning, we can determine Bob's score in O(1) time for any given score of Alice's, avoiding recalculation. This allows us to solve the problem in a single pass through the array.
**Time:** O(n) - The algorithm consists of two separate, non-nested loops that each iterate through the array once. The total time is proportional to `n`, making it a linear time solution. · **Space:** O(1) - We only use a few variables to store the total score and Alice's running score, regardless of the input size.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Optimal in terms of time and space complexity.
**Cons:** Requires a small mathematical insight to simplify the score comparison, which might not be immediately obvious.
### Explanation
A more efficient solution avoids the nested loops by using a prefix sum concept. The core idea is based on the observation that for any split point `k`, the sum of Alice's score and Bob's score is always equal to the total score of the game.

`aliceScore(k) + bobScore(k) = totalScore`

The condition we need to satisfy is `aliceScore(k) > bobScore(k)`. We can substitute `bobScore(k)`:

`aliceScore(k) > totalScore - aliceScore(k)`
`2 * aliceScore(k) > totalScore`

This simplified inequality allows for a much faster algorithm:
1.  First, we make a single pass through the `possible` array to calculate the `totalScore`.
2.  Then, we make a second pass. We iterate from `i = 0` to `n-2` (since Bob must play at least one level). In this loop, we maintain a running `aliceScore` which is the prefix sum of scores up to level `i`. 
3.  At each step `i`, we check if `2 * aliceScore > totalScore`. If it is, we have found the minimum number of levels Alice needs to play, which is `i+1`. We return `i+1`.
4.  If the loop finishes without this condition ever being true, it's impossible for Alice to win, so we return `-1`.

```java
class Solution {
    public int minimumLevels(int[] possible) {
        int n = possible.length;
        int totalScore = 0;
        // First, calculate the total score if one person played all levels.
        for (int p : possible) {
            if (p == 0) {
                totalScore--;
            } else {
                totalScore++;
            }
        }

        int aliceScore = 0;
        // Iterate through all possible split points.
        // Alice plays i+1 levels.
        for (int i = 0; i < n - 1; i++) {
            if (possible[i] == 0) {
                aliceScore--;
            } else {
                aliceScore++;
            }
            
            // Bob's score is the total score minus Alice's score.
            int bobScore = totalScore - aliceScore;
            
            if (aliceScore > bobScore) {
                return i + 1;
            }
        }
        
        return -1;
    }
}
```
### Algorithm
*   First, calculate the `totalScore` for the entire game by iterating through the `possible` array once. Add `1` for each `1` and subtract `1` for each `0`.
*   Initialize `aliceScore = 0`.
*   Iterate with an index `i` from `0` to `n-2`. This index represents the last level Alice plays.
*   In each iteration, update `aliceScore` by adding the points for level `i`.
*   Use the pre-calculated `totalScore` and the current `aliceScore` to find `bobScore` in O(1) time: `bobScore = totalScore - aliceScore`.
*   Check if `aliceScore > bobScore`. This is equivalent to checking if `2 * aliceScore > totalScore`.
*   If the condition is true, Alice has played `i+1` levels. This is the minimum required, so return `i+1`.
*   If the loop completes without the condition being met, return `-1`.

# Solutions
### Java

```java
class Solution {
public
  int minimumLevels(int[] possible) {
    int s = 0;
    for (int x : possible) {
      s += x == 0 ? -1 : 1;
    }
    int t = 0;
    for (int i = 1; i < possible.length; ++i) {
      t += possible[i - 1] == 0 ? -1 : 1;
      if (t > s - t) {
        return i;
      }
    }
    return -1;
  }
}

```

### Python

```python
class Solution:
    def minimumLevels(self, possible: List[int]) -> int: s = sum(- 1 if x == 0 else 1 for x in possible) t = 0 for i, x in enumerate(possible[: - 1], 1): t += - 1 if x == 0 else 1 if t > s - t: return i return - 1

```

### CPP

```cpp
class Solution {
public:
  int minimumLevels(vector<int> &possible) {
    int s = 0;
    for (int x : possible) {
      s += x == 0 ? -1 : 1;
    }
    int t = 0;
    for (int i = 1; i < possible.size(); ++i) {
      t += possible[i - 1] == 0 ? -1 : 1;
      if (t > s - t) {
        return i;
      }
    }
    return -1;
  }
};

```