# 2599. [Make the Prefix Sum Non-negative](<https://leetcode.com/problems/make-the-prefix-sum-non-negative>)

*All prompts are owned by LeetCode. To view the prompt, click the title link above.*

*[Back to top](<../README.md>)*

------

> *First completed : February 10, 2025*
>
> *Last updated : February 10, 2025*

------

> **Related Topics** : **[Array](<by_topic/Array.md>), [Greedy](<by_topic/Greedy.md>), [Heap (Priority Queue)](<by_topic/Heap (Priority Queue).md>)**
>
> **Acceptance Rate** : **51.66 %**

------

> This to me is a straight forwards prefix sum array question where
> the only difference is that you need to track all negative numbers
> that you cross. This is since the edge case is when the most recent
> negative value you come across at the point in which the prefix sum
> goes negative is not enough to compensate, or if the previous few
> sum to less of an abs difference than a single earlier value, thus
> wasting moves.
> 

------

## Solutions

- [m2599.py](<../my-submissions/m2599.py>)
### Python
#### [m2599.py](<../my-submissions/m2599.py>)
```Python
class Solution:
    def makePrefSumNonNegative(self, nums: List[int]) -> int:
        moves = 0
        curr_sum = 0

        # Min heap keeps the largest abs val neg numbers at top
        neg_hp = []

        for num in nums :
            if num < 0 :
                heapq.heappush(neg_hp, num)

            curr_sum += num
            if curr_sum < 0 :
                moves += 1
                curr_sum -= heapq.heappop(neg_hp)

        return moves
```