You are given a 0-indexed integer array nums. You can apply the following operation any number of times:
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.
Example 1:
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:
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 <= 105-109 <= nums[i] <= 109Problem Overview: You are given an integer array where you may move any element to the end of the array. The goal is to perform the minimum number of such moves so that every prefix sum of the final array is non‑negative.
Approach 1: Naive Greedy Scan (O(n²) time, O(1) space)
A straightforward idea is to process the array from left to right while maintaining the running prefix sum. Whenever the sum becomes negative, search the previously seen elements and choose one negative number to move to the end so the prefix becomes valid again. This requires repeatedly scanning earlier elements to decide which value to remove, which leads to quadratic time in the worst case. The approach shows the greedy intuition: removing the most harmful negative number fixes the prefix sum.
Approach 2: Greedy + Priority Queue (Min Heap) (O(n log n) time, O(n) space)
The optimal strategy formalizes the greedy idea using a heap (priority queue). Iterate through the array while maintaining a running prefix sum. Push every number into a min heap. If the prefix sum becomes negative, remove the smallest element from the heap (the most negative value). That element is effectively moved to the end of the array, and the prefix sum is corrected by subtracting it from the running total.
The key insight: when the prefix sum drops below zero, the best element to postpone is the most negative one seen so far. Removing a less negative value would reduce the damage less and may require additional moves later. A min heap guarantees that the worst value can be removed in O(log n) time.
Algorithm outline:
1. Iterate through the array and maintain prefixSum.
2. Push each value into a min heap.
3. If prefixSum < 0, pop the smallest value from the heap and subtract it from the prefix sum.
4. Increment the move counter.
This greedy approach works because every correction postpones the element that harms the prefix sum the most, ensuring the minimum number of operations. The heap tracks all candidates efficiently while scanning the array once.
Recommended for interviews: The greedy + priority queue approach is what interviewers expect. Explaining the naive idea first shows you understand why the most negative element must be removed. Implementing the heap-based solution demonstrates the ability to optimize the greedy strategy to O(n log n) time.
We use a variable s to record the prefix sum of the current array.
Traverse the array nums, add the current element x to the prefix sum s. If x is a negative number, add x to the min heap. If s is negative at this time, greedily take out the smallest negative number and subtract it from s, and add one to the answer. Finally, return the answer.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Greedy Scan | O(n²) | O(1) | Useful for understanding the greedy intuition by manually selecting a negative element when prefix sum becomes negative. |
| Greedy + Min Heap (Priority Queue) | O(n log n) | O(n) | Best general solution. Efficiently tracks the most negative element while scanning the array once. |
2599. Make the Prefix Sum Non-negative - Week 2/4 Leetcode February Challenge • Programming Live with Larry • 295 views views
Watch 1 more video solutions →Practice Make the Prefix Sum Non-negative with our built-in code editor and test cases.
Practice on FleetCode