Watch 2 video solutions for Make the Prefix Sum Non-negative, a medium level problem involving Array, Greedy, Heap (Priority Queue). This walkthrough by Programming Live with Larry has 295 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |