Skip to main content
Talentd

Make the Prefix Sum Non-negative - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedyHeap (Priority Queue)7 min readAsked at: Microsoft
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums. You can apply the following operation any number of times:

  • Pick any element from 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] <= 109

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Greedy ScanO(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.

Video Solution

2599. Make the Prefix Sum Non-negative - Week 2/4 Leetcode February Challenge • Programming Live with Larry • 308 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Make the Prefix Sum Non-negative easy or hard?
Make the Prefix Sum Non-negative is a medium‑difficulty problem. The challenge lies in recognizing the greedy insight that the most negative element should be postponed when the prefix becomes invalid. Implementing the solution with a heap keeps the algorithm efficient.
Make the Prefix Sum Non-negative Python/Java solution
The standard implementation maintains a running prefix sum and a min heap. For each number, add it to the sum and push it into the heap. If the sum becomes negative, pop the smallest element and subtract it from the sum while counting the move. The same greedy logic works in Python, Java, C++, Go, and TypeScript using their built‑in priority queue or heap libraries.
How to solve Make the Prefix Sum Non-negative in O(n)?
A true O(n) solution is difficult because you must repeatedly identify the most negative value among previously seen elements. The practical optimal method uses a min heap to perform that selection efficiently. The overall complexity becomes O(n log n) due to heap insertions and removals.
What is the best approach for Make the Prefix Sum Non-negative?
The best approach uses a greedy strategy with a min heap (priority queue). Traverse the array while maintaining the running prefix sum and push elements into the heap. Whenever the prefix sum becomes negative, remove the smallest element (most negative value) from the heap and treat it as moved to the end. This ensures the prefix sum remains non‑negative with the minimum number of moves in O(n log n) time.
Is Make the Prefix Sum Non-negative asked at Google/Amazon/Meta?
Greedy problems combined with heaps frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve maintaining prefix constraints or postponing harmful elements are common interview patterns. Practicing this problem helps reinforce those greedy + priority queue techniques.
What data structure is used in Make the Prefix Sum Non-negative?
A min heap (priority queue) is the key data structure. It stores all elements processed so far so the algorithm can quickly remove the smallest value when the prefix sum becomes negative. This allows the algorithm to always postpone the most harmful element efficiently.
What is the time complexity of Make the Prefix Sum Non-negative?
The optimal solution runs in O(n log n) time and O(n) space. Each element is inserted into a priority queue once, and in the worst case several elements may be removed from the heap. Heap operations take O(log n), while the array is scanned only once.

Ready to solve this problem?

Practice Make the Prefix Sum Non-negative with our built-in code editor and test cases.

Practice on FleetCode
Previous

Furthest Building You Can Reach

Next

Maximum Transactions Without Negative Balance