LeetCode 2599 - Make the Prefix Sum Non-negative

The problem asks us to manipulate an array of integers, nums, so that its prefix sums are never negative. A prefix sum at index i is simply the sum of all elements from the start of the array up to i.

leetcodemediumarraygreedyheap-(priority-queue)

LeetCode Problem 2599

Difficulty: 🟡 Medium
Topics: Array, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to manipulate an array of integers, nums, so that its prefix sums are never negative. A prefix sum at index i is simply the sum of all elements from the start of the array up to i. The only operation allowed is to take any element in nums and move it to the end of the array. We need to determine the minimum number of such operations to achieve a non-negative prefix sum array.

In other words, we want the running total of the array to never drop below zero, and we can do this by reordering negative numbers toward the end. The problem guarantees a solution always exists, meaning it is always possible to rearrange the array to meet the requirement.

The constraints are significant: the array length can be up to 100,000, and individual elements can range from -1,000,000,000 to 1,000,000,000. This tells us that any brute-force solution that considers every permutation is infeasible, and we need a greedy or priority-based approach. Key edge cases include arrays that are already non-negative, arrays that start with large negative numbers, and arrays containing all negatives.

Approaches

The brute-force approach would be to repeatedly check the prefix sums, and whenever a prefix becomes negative, try moving elements around to fix it. This approach is correct in principle, but it is extremely slow because it may involve moving elements multiple times and recalculating prefix sums, resulting in a factorial time complexity.

The key insight for an optimal solution is to process the array from left to right, maintaining a running prefix sum. Whenever the prefix sum becomes negative, we know we need to "remove" some large negative contribution that caused it to drop below zero. Using a max-heap (priority queue) of negative numbers encountered so far, we can greedily remove the largest negative numbers (by absolute value) to the end, incrementing the operation count each time. This ensures the prefix sum remains non-negative in an efficient manner.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Repeatedly check and move elements, recalculating prefix sums each time. Too slow for n up to 10^5.
Optimal O(n log n) O(n) Use a max-heap to store negative numbers, greedily "remove" largest negatives when prefix sum drops below zero.

Algorithm Walkthrough

  1. Initialize a variable prefix_sum to 0 to track the running prefix sum. Initialize operations to 0 to count the number of moves. Initialize an empty max-heap negatives_heap to store negative numbers we encounter.
  2. Iterate through each element in nums.
  3. Add the current element to prefix_sum.
  4. If the current element is negative, push it into negatives_heap. In Python, to use a max-heap, store negative values so the largest negative becomes the smallest in the min-heap implementation.
  5. If prefix_sum becomes negative, repeatedly pop the largest negative number from the heap, add its absolute value back to prefix_sum (as if removing it from the prefix and moving it to the end), and increment operations. Repeat until prefix_sum is non-negative.
  6. Continue until all elements are processed.
  7. Return operations.

Why it works: The invariant maintained is that prefix_sum is non-negative after removing the largest negative elements whenever it drops below zero. Greedily removing the largest negative ensures we minimize the number of moves because removing smaller negatives would not restore the prefix sum efficiently.

Python Solution

from typing import List
import heapq

class Solution:
    def makePrefSumNonNegative(self, nums: List[int]) -> int:
        prefix_sum = 0
        operations = 0
        max_heap = []  # store negatives as negative numbers for max-heap behavior
        
        for num in nums:
            prefix_sum += num
            if num < 0:
                heapq.heappush(max_heap, num)
            while prefix_sum < 0:
                largest_negative = heapq.heappop(max_heap)
                prefix_sum -= largest_negative  # subtracting a negative increases the sum
                operations += 1
        
        return operations

This implementation maintains a running prefix sum and a heap of negative numbers. Whenever the sum drops below zero, it removes the largest negative number to restore non-negativity, counting each removal as an operation.

Go Solution

package main

import (
    "container/heap"
)

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] > h[j] } // max-heap
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func makePrefSumNonNegative(nums []int) int {
    prefixSum := 0
    operations := 0
    maxHeap := &IntHeap{}
    heap.Init(maxHeap)
    
    for _, num := range nums {
        prefixSum += num
        if num < 0 {
            heap.Push(maxHeap, num)
        }
        for prefixSum < 0 {
            largestNegative := heap.Pop(maxHeap).(int)
            prefixSum -= largestNegative
            operations++
        }
    }
    
    return operations
}

In Go, we implement a max-heap by defining a custom heap type with Less inverted. The rest of the logic mirrors the Python solution.

Worked Examples

Example 1: nums = [2,3,-5,4]

Step num prefix_sum heap operations
1 2 2 [] 0
2 3 5 [] 0
3 -5 0 [-5] 0
4 4 4 [-5] 0

Output: 0

Example 2: nums = [3,-5,-2,6]

Step num prefix_sum heap operations
1 3 3 [] 0
2 -5 -2 [-5] prefix_sum<0 → remove -5 → prefix_sum=3
3 -2 1 [-2] 1
4 6 7 [-2] 1

Output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Each negative number is pushed/popped from the heap at most once. Each heap operation takes O(log n).
Space O(n) Heap can contain at most all negative numbers in nums.

The complexity is efficient enough for n up to 10^5.

Test Cases

# Provided examples
assert Solution().makePrefSumNonNegative([2,3,-5,4]) == 0  # no operation needed
assert Solution().makePrefSumNonNegative([3,-5,-2,6]) == 1  # one operation

# Edge cases
assert Solution().makePrefSumNonNegative([-1,-2,-3,10]) == 3  # all negatives moved to end
assert Solution().makePrefSumNonNegative([5, -1, -2, 3]) == 1  # single negative adjustment
assert Solution().makePrefSumNonNegative([0,0,0,0]) == 0  # zeros, no operations
assert Solution().makePrefSumNonNegative([10**9, -10**9]) == 1  # large numbers
assert Solution().makePrefSumNonNegative([1]) == 0  # single element positive
assert Solution().makePrefSumNonNegative([-1]) == 1  # single element negative
Test Why
[2,3,-5,4] Already non-negative prefix sum
[3,-5,-2,6] Requires one operation for first negative drop
[-1,-2,-3,10] All negatives at start, largest negative removals needed
[5,-1,-2,3] Mixed numbers, requires selective negative removal
[0,0,0,0] Edge case with zeros, no effect on prefix sum
[109, -109] Edge case with very large numbers to check overflow handling
[1] Single positive element
[-1] Single negative element requires operation

Edge Cases

First, consider arrays with all negative numbers followed by a large positive number. This can test whether the algorithm correctly moves multiple negatives while preserving a non-negative running sum.

Second, consider arrays starting with a large negative number, followed by smaller positives. A naive algorithm might fail if it does not greedily remove the largest negative first.

Third, arrays with zeros only. Zeros do not affect