Problem Description

You have a 0-indexed integer array nums. You can perform the following operation as many times as needed:

• Pick any element from nums and move it to the end of the array.

A prefix sum array is defined as an array prefix where each element prefix[i] equals the sum of all elements from index 0 to i in the original array. In other words, prefix[i] = nums[0] + nums[1] + ... + nums[i].

Your goal is to find the minimum number of operations needed to rearrange the array such that no element in its prefix sum array is negative.

For example, if nums = [3, -5, 2]:

• Initial prefix sum array: [3, -2, 0] (has negative value -2)
• After moving -5 to the end: nums = [3, 2, -5]
• New prefix sum array: [3, 5, 0] (all non-negative)
• This takes 1 operation

The problem guarantees that it's always possible to achieve a non-negative prefix sum array through these operations.

The solution uses a greedy approach with a min heap. As we traverse the array and calculate running prefix sums, whenever the sum becomes negative, we greedily "undo" the most negative numbers we've seen so far (simulating moving them to the end) until the prefix sum becomes non-negative again. The heap keeps track of negative numbers encountered, allowing us to always remove the smallest (most negative) value first for optimal results.

Intuition

When we encounter a negative prefix sum while traversing the array, we need to fix it. The key insight is that moving an element to the end effectively "removes" it from all prefix sums up to that point. So when our running sum becomes negative, we want to remove some negative numbers we've already included to make the sum non-negative again.

But which negative numbers should we remove? Here's where the greedy choice comes in: we should always remove the most negative number available. Why? Because removing the smallest (most negative) number gives us the maximum increase in our prefix sum with just one operation. This minimizes the total number of operations needed.

Consider this: if our prefix sum is -3 and we have two negative numbers we could remove: -5 and -2. Removing -5 would change our sum from -3 to -3 - (-5) = 2, making it positive in one operation. Removing -2 would only get us to -1, still requiring another operation.

This naturally leads us to use a min heap to track all negative numbers we encounter. Whenever our prefix sum goes negative, we greedily pop the smallest value from the heap (the most negative number) and "undo" its contribution to the sum. We repeat this until the prefix sum becomes non-negative.

The beauty of this approach is that we're simulating the rearrangement without actually moving elements. Each pop from the heap represents moving that negative number to the end of the array, and we count each pop as one operation. The algorithm ensures we always make the optimal choice at each step, giving us the minimum number of operations needed.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a greedy algorithm with a min heap to efficiently track and remove the most negative numbers when needed.

Here's the step-by-step walkthrough:

1. Initialize data structures:

   • h = []: A min heap to store negative numbers encountered
   • ans = 0: Counter for the number of operations
   • s = 0: Running prefix sum

2. Process each element in the array:

   for x in nums:
       s += x  # Update the running prefix sum

3. Track negative numbers:

   if x < 0:
       heappush(h, x)  # Add negative numbers to the min heap

   We only store negative numbers because these are the only ones we might need to move to fix negative prefix sums.

4. Fix negative prefix sums greedily:

   while s < 0:
       s -= heappop(h)  # Remove the most negative number
       ans += 1         # Count this as one operation

   When the prefix sum becomes negative, we repeatedly:

   • Pop the smallest (most negative) value from the heap
   • Subtract it from s (since we're "removing" it from the prefix)
   • Increment our operation counter

   Note that subtracting a negative number increases s. For example, if s = -3 and we pop -5, then s = -3 - (-5) = 2.

5. Return the total operations: After processing all elements, ans contains the minimum number of moves needed.

Time Complexity: O(n log n) where n is the length of the array. Each element is processed once, and heap operations take O(log n) time.

Space Complexity: O(n) in the worst case if all elements are negative and stored in the heap.

The algorithm ensures optimality because at each decision point, we make the locally optimal choice (removing the most negative number), which leads to the globally optimal solution for this problem.

Example Walkthrough

Let's walk through the algorithm with nums = [2, -3, -8, 4, -6, 1].

Initial Setup:

• Min heap h = []
• Operations count ans = 0
• Running sum s = 0

Step 1: Process element 2

• Update sum: s = 0 + 2 = 2
• Since 2 is positive, don't add to heap
• Sum is positive, no fix needed
• State: s = 2, h = [], ans = 0

Step 2: Process element -3

• Update sum: s = 2 + (-3) = -1
• Since -3 is negative, add to heap: h = [-3]
• Sum is negative! Fix it:
  • Pop smallest from heap: pop -3
  • Update sum: s = -1 - (-3) = 2
  • Increment operations: ans = 1
• State: s = 2, h = [], ans = 1

Step 3: Process element -8

• Update sum: s = 2 + (-8) = -6
• Since -8 is negative, add to heap: h = [-8]
• Sum is negative! Fix it:
  • Pop smallest from heap: pop -8
  • Update sum: s = -6 - (-8) = 2
  • Increment operations: ans = 2
• State: s = 2, h = [], ans = 2

Step 4: Process element 4

• Update sum: s = 2 + 4 = 6
• Since 4 is positive, don't add to heap
• Sum is positive, no fix needed
• State: s = 6, h = [], ans = 2

Step 5: Process element -6

• Update sum: s = 6 + (-6) = 0
• Since -6 is negative, add to heap: h = [-6]
• Sum is 0 (non-negative), no fix needed
• State: s = 0, h = [-6], ans = 2

Step 6: Process element 1

• Update sum: s = 0 + 1 = 1
• Since 1 is positive, don't add to heap
• Sum is positive, no fix needed
• Final state: s = 1, h = [-6], ans = 2

Result: Minimum operations needed = 2

The algorithm effectively simulated moving -3 and -8 to the end of the array. The resulting arrangement would be [2, 4, -6, 1, -3, -8] with prefix sums [2, 6, 0, 1, -2, -10]. Note that we still have negative prefix sums at the end, but this is acceptable since we only care about maintaining non-negative prefix sums for the elements in their final positions before the moved elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm iterates through the array once with n elements. For each element:

• Adding an element to the array takes O(1) time
• If the element is negative, it's pushed to the heap in O(log k) time where k is the current heap size
• The while loop may execute multiple times, and each heappop operation takes O(log k) time

In the worst case, all negative numbers could be pushed to the heap and then popped, resulting in up to n heap operations. Since each heap operation (push or pop) takes O(log n) time in the worst case when the heap contains up to n elements, the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space is dominated by the min-heap h, which in the worst case stores all negative numbers from the input array. If all n elements are negative, the heap would contain up to n elements, resulting in O(n) space complexity. The other variables (ans, s, x) use constant space O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusion About the "Removal" Operation

The Issue: A common misunderstanding is thinking that when we pop a negative number from the heap and "remove" it, we're deleting it from the array entirely. This leads to confusion about why we subtract the popped value from the prefix sum instead of just recalculating.

What Actually Happens: The operation doesn't delete elements; it moves them to the end of the array. When we pop a value from the heap, we're simulating that this element will be moved to the end later, so we need to exclude it from our current prefix sum calculation.

Correct Understanding:

# When we do this:
most_negative = heapq.heappop(negative_heap)
prefix_sum -= most_negative  # This is correct!

# We're effectively saying: "pretend this element isn't here yet"
# Since most_negative is negative, subtracting it increases prefix_sum
# Example: prefix_sum = -2, most_negative = -5
# prefix_sum = -2 - (-5) = 3

Pitfall 2: Attempting to Track Element Positions

The Issue: Some might try to track which specific elements have been "moved" and their original positions, thinking this information is necessary for the solution.

Why It's Wrong:

# INCORRECT approach:
moved_indices = set()
for i, x in enumerate(nums):
    if should_move:
        moved_indices.add(i)  # Unnecessary complexity!

The Solution: The beauty of this greedy approach is that we don't need to track positions. We only need to know:

1. Which negative values we've encountered (stored in heap)
2. How many we've decided to move (the count)

The actual rearrangement details are irrelevant for counting operations.

Pitfall 3: Forgetting to Handle Only Negative Numbers in Heap

The Issue: Adding all numbers to the heap, not just negative ones:

# INCORRECT:
for current_num in nums:
    heapq.heappush(negative_heap, current_num)  # Wrong! Adds positives too

Why It Matters:

• We never need to move positive numbers to fix negative prefix sums
• Moving positive numbers would only make prefix sums smaller (counterproductive)
• Including them wastes space and could lead to incorrect logic if we accidentally pop a positive number

Correct Approach:

if current_num < 0:
    heapq.heappush(negative_heap, current_num)  # Only negatives

Pitfall 4: Not Understanding the Heap's Role

The Issue: Using a different data structure or not understanding why a min heap specifically is needed:

# INCORRECT alternatives:
negative_list = []  # Using a list and sorting each time - O(n²log n)
negative_stack = []  # LIFO doesn't give us the most negative element

Why Min Heap is Optimal:

• We need the most negative number (minimum value) quickly
• Min heap gives us O(log n) access to the smallest element
• This ensures we make the maximum impact on the prefix sum with each operation
• Removing -10 is better than removing -1 when trying to fix a negative prefix sum