Problem

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.

Examples

Example 1:

1
2
3
4

Input: nums = [2,3,-5,4]
Output: 0
Explanation: we do not need to do any operations.
The array is [2,3,-5,4]. The prefix sum array is [2, 5, 0, 4].

Example 2:

1
2
3
4

Input: nums = [3,-5,-2,6]
Output: 1
Explanation: we can do one operation on index 1.
The array after the operation is [3,-2,6,-5]. The prefix sum array is [3, 1, 7, 2].

Constraints:

  • 1 <= nums.length <= 10^5
  • -109 <= nums[i] <= 10^9

Solution

Method 1 – Greedy with Min-Heap (Priority Queue)

Intuition

The key idea is to keep the prefix sum non-negative as we iterate through the array. If the prefix sum becomes negative, we need to “move” the most negative number seen so far to the end, which is equivalent to removing its effect from the prefix sum up to that point. We use a min-heap (priority queue) to efficiently track the largest negative numbers we’ve included so far.

Approach

  1. Initialize a variable pre for the running prefix sum and a min-heap to store negative numbers.
  2. Iterate through the array:
    • Add the current number to pre.
    • If the number is negative, push it into the min-heap.
    • If pre becomes negative:
      • Pop the smallest (most negative) number from the heap and “move” it to the end (i.e., remove its effect from pre).
      • Increment the operation count.
      • Repeat until pre is non-negative.
  3. Return the operation count.

Code

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

class Solution {
public:
    int makePrefSumNonNegative(vector<int>& nums) {
        priority_queue<int> pq;
        long long pre = 0;
        int ans = 0;
        for (int x : nums) {
            pre += x;
            if (x < 0) pq.push(-x);
            while (pre < 0 && !pq.empty()) {
                pre += pq.top();
                pq.pop();
                ans++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func makePrefSumNonNegative(nums []int) int {
    h := &IntHeap{}
    heap.Init(h)
    pre, ans := 0, 0
    for _, x := range nums {
        pre += x
        if x < 0 {
            heap.Push(h, -x)
        }
        for pre < 0 && h.Len() > 0 {
            pre += heap.Pop(h).(int)
            ans++
        }
    }
    return ans
}
// type IntHeap and heap interface methods omitted for brevity
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int makePrefSumNonNegative(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long pre = 0;
        int ans = 0;
        for (int x : nums) {
            pre += x;
            if (x < 0) pq.offer(-x);
            while (pre < 0 && !pq.isEmpty()) {
                pre += pq.poll();
                ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun makePrefSumNonNegative(nums: IntArray): Int {
        val pq = java.util.PriorityQueue<Int>()
        var pre = 0L
        var ans = 0
        for (x in nums) {
            pre += x
            if (x < 0) pq.add(-x)
            while (pre < 0 && pq.isNotEmpty()) {
                pre += pq.poll()
                ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def makePrefSumNonNegative(self, nums: list[int]) -> int:
        import heapq
        pre = 0
        ans = 0
        heap = []
        for x in nums:
            pre += x
            if x < 0:
                heapq.heappush(heap, x)
            while pre < 0 and heap:
                pre -= heapq.heappop(heap)
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn make_pref_sum_non_negative(nums: Vec<i32>) -> i32 {
        use std::collections::BinaryHeap;
        let mut heap = BinaryHeap::new();
        let mut pre: i64 = 0;
        let mut ans = 0;
        for &x in &nums {
            pre += x as i64;
            if x < 0 {
                heap.push(-x);
            }
            while pre < 0 && !heap.is_empty() {
                pre += heap.pop().unwrap() as i64;
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    makePrefSumNonNegative(nums: number[]): number {
        const heap: number[] = [];
        let pre = 0, ans = 0;
        for (const x of nums) {
            pre += x;
            if (x < 0) heap.push(x);
            heap.sort((a, b) => a - b);
            while (pre < 0 && heap.length > 0) {
                pre -= heap.shift()!;
                ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), because each negative number may be pushed and popped from the heap, and heap operations are O(log n).
  • 🧺 Space complexity: O(n), for storing up to all negative numbers in the heap.