Minimum levels to gain more points

Array Prefix Sum

40.1% acceptance

Feb 25, 2026

You are given a binary array possible of length n. Alice and Bob are playing a game that consists of n levels. If possible[i] == 0, the ith level is impossible to clear for both players. A player gains 1 point on clearing a level and loses 1 point if the player fails to clear it. Alice will play some levels starting from 0, after which Bob will play for the rest. Return the minimum number of levels Alice should play to gain more points than Bob. If this is not possible, return -1.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_levels(possible: Vec<i32>) -> i32 {
    let n = possible.len();
    let score = |v: i32| if v == 1 { 1i64 } else { -1 };
    let total: i64 = possible.iter().map(|&v| score(v)).sum();
    let mut alice = 0i64;
    for i in 0..n-1 {
      alice += score(possible[i]);
      let bob = total - alice;
      if alice > bob { return (i + 1) as i32; }
    }
    -1
  }
}