All prompts are owned by LeetCode. To view the prompt, click the title link above.
First completed : February 10, 2025
Last updated : February 10, 2025
Related Topics : Array, Greedy, Heap (Priority Queue)
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.
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