Make a positive array

Array Greedy Prefix Sum

35.3% acceptance

Mar 31, 2026

You are given an array nums. An array is considered positive if the sum of all numbers in each subarray with more than two elements is positive. You can perform the following operation any number of times: Replace one element in nums with any integer between -1018 and 1018. Find the minimum number of operations needed to make nums positive.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn make_array_positive(nums: Vec<i32>) -> i32 {
    // Every subarray of length >= 3 must have positive sum.
    // Equivalent: for prefix sums, prefix[p] > prefix[q] for all p - q >= 3.
    // Greedy: process segments. When violated, replace the latest element
    // (setting it to huge value), which restarts the segment.
    let n = nums.len();
    if n < 3 { return 0; }
    
    let mut ops = 0i32;
    let mut seg_start = 0usize;
    
    loop {
      let mut local_prefix = vec![0i64];
      let mut max_prefix = i64::MIN;
      let mut violated = false;
      
      for j in seg_start..n {
        local_prefix.push(local_prefix.last().unwrap() + nums[j] as i64);
        let p = local_prefix.len() - 1;
        
        if p >= 3 {
          let val = local_prefix[p - 3];
          if val > max_prefix {
            max_prefix = val;
          }
          if local_prefix[p] <= max_prefix {
            ops += 1;
            seg_start = j + 1;
            violated = true;
            break;
          }
        }
      }
      
      if !violated {
        break;
      }
    }
    
    ops
  }
}