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.

Description Hints 2 Solution Video 10:53

2599. Make the Prefix Sum Non-negative

Medium51.9% acceptance1 companyPremium elsewhere, free here

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Asked at 1 company

Microsoft

Topics

Hints open one at a time

Hint 1

There will always be a way to make the prefix sum non-negative. How can we use that?

Hint 2

Loop over the array keeping the prefix sum. Whenever it goes negative, move the smallest number you have seen to the end.

10:53

Still stuck?Read the written solution, or watch a walkthrough.

Open solution