Make the prefix sum non negative

Array Greedy Heap (Priority Queue)

51.9% acceptance

Mar 31, 2026

You are given a 0-indexed integer array nums. You can apply the following operation any number of times: Pick any element from nums and put it at the end of nums. The prefix sum array of nums is an array prefix of the same length as nums such that prefix[i] is the sum of all the integers nums[j] where j is in the inclusive range [0, i]. Return the minimum number of operations such that the prefix sum array does not contain negative integers. The test cases are generated such that it is always possible to make the prefix sum array non-negative.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn make_pref_sum_non_negative(nums: Vec<i32>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let mut heap: BinaryHeap<Reverse<i64>> = BinaryHeap::new();
    let mut prefix: i64 = 0;
    let mut ops = 0;
    for &num in &nums {
      let v = num as i64;
      if v < 0 {
        heap.push(Reverse(v));
      }
      prefix += v;
      while prefix < 0 {
        if let Some(Reverse(smallest)) = heap.pop() {
          prefix -= smallest; // smallest is negative, so subtracting adds
          ops += 1;
        }
      }
    }
    ops
  }
}