2599. Make the Prefix Sum Non-negative


Problem Description

This problem presents an optimization challenge with an integer array nums. The main objective is to transform this array so that its prefix sum array contains no negative integers. To clarify, a prefix sum array is one where each element at index i is the total sum of all elements from the start of the array to that index, inclusive. The transformation of the array nums can only be achieved through a series of operations, each of which involves selecting one element from the array and moving it to the end.

The task is to figure out the minimum number of such operations needed to ensure that all the sums in the prefix sum array are non-negative. It is confirmed that there is always a way to rearrange the elements of the initial array in order to achieve this non-negative prefix sum property.

Intuition

The solution hinges on the greedy algorithm and a priority queue (which is implemented as a min heap in Python). The intuition behind the greedy approach is that by continually relocating the most negative value from the array to the end, we decrease the sum in the most effective way possible, which in turn quickly leads to a non-negative prefix sum at each step.

We start by traversing the array and calculating the prefix sums using a running sum variable s. When we come across a negative number, we put it into our priority queue (min heap). If at any point our running sum s becomes negative, it means our current prefix sum array contains negative values. In order to fix this, we repeatedly remove the smallest (most negative) number from the heap, since removing this number will give us the largest positive change towards making the sum non-negative. The number of times we need to remove an element from the heap to make the running sum non-negative at each step is added to our answer total, ans.

The loop structure ensures that we only pop from the heap when necessary, i.e., when the running sum is negative. This combination of a greedy approach with a priority queue allows us to efficiently manage and adjust the most negative elements which are contributing to a negative prefix sum. The counting of heap removals gives us the minimum number of operations required to prevent any negatives in the prefix sum array.

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

Solution Approach

The provided solution uses a greedy approach in conjunction with a priority queue (min heap) data structure from Python's heapq library, which enables efficient retrieval of the smallest element.

Following are step-by-step implementation details:

  1. Initialize an empty min heap h, an accumulator ans to count the number of moves, and a sum s to keep track of the prefix sum.

  2. Iterate over each element x in the array nums:

    • Add the current element to the prefix sum s (= s + x).
    • If x is negative, push it onto the min heap h using heappush(h, x).
  3. After each addition of an element to s, check if s is negative:

    • While s is negative, repeatedly:
      • Pop the smallest (most negative) element from the min heap h using heappop(h).
      • Subtract the popped element from s, which will make s less negative or non-negative.
      • Increment ans by 1 representing an operation.
  4. Once all elements have been processed, return ans, which now contains the count of the minimum number of operations needed to ensure the prefix sum array is non-negative.

The algorithm efficiently rearranges the elements by virtually moving the most negative values to the end of the array, thus not needing to manipulate the array directly. Instead, we operate on the prefix sum and extract the negative impact whenever it threatens to pull the sum below zero.

As we traverse nums, we accumulate negative values into the min heap. Popping from the min heap gives us the smallest negative number quickly, which is the ideal candidate to "move" to the end (in a virtual sense) because its removal will have the biggest immediate positive (or least negative) impact on s.

The solution approach takes advantage of the properties of a min heap, where ensuring the heap structure after each insertion or deletion operation (i.e., heappush and heappop) takes O(log n) time, thus each operation on the heap is efficient even as nums grows in size.

In summary, the solution applies algorithms and data structures (greedy technique and priority queue) to cleverly and efficiently find the minimum set of adjustments to nums that guarantees a non-negative prefix sum array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the following small example array nums: [3, -7, 4, -2, 1, 2]

  1. We initialize the following:

    • Min heap h: []
    • Operation counter ans: 0
    • Prefix sum s: 0
  2. Process the array nums:

    • For the first element (3):
      • s becomes 3 (0 + 3). s is non-negative, so no need for changes.
      • Min heap h remains empty.
    • For the second element (-7):
      • s becomes -4 (3 - 7). s is negative.
      • We push -7 onto the min heap h: [-7]
      • Since s is negative, we pop from h (-7), add it back to s (+7), and increment ans by 1.
      • s is now 3 (-4 + 7), and ans is 1.
      • Min heap h is now empty.
    • For the third element (4):
      • s becomes 7 (3 + 4). s is non-negative.
      • Min heap h remains empty.
    • For the fourth element (-2):
      • s becomes 5 (7 - 2). s is non-negative.
      • We push -2 onto the min heap h: [-2]
    • For the fifth element (1):
      • s becomes 6 (5 + 1). s is non-negative.
      • Min heap h remains as: [-2]
    • For the sixth element (2):
      • s becomes 8 (6 + 2). s is non-negative.
      • Min heap h remains as: [-2]
  3. Since we've finished processing nums and s is non-negative, ans remains at 1.

  4. Thus, the minimum number of operations needed to ensure the prefix sum array is non-negative for nums is 1.

In this example, only one operation was needed, which involved moving the -7 to the end of the array to ensure all prefix sums were non-negative. This step is conceptual as we actually just remove the negative influence of -7 from the running sum s.

Solution Implementation

1from heapq import heappush, heappop
2from typing import List
3
4class Solution:
5    def makePrefSumNonNegative(self, nums: List[int]) -> int:
6        # A min-heap to store the negative numbers encountered
7        min_heap = []
8      
9        # The variable `total_operations` represents the number of operations performed to make the prefix sums non-negative
10        total_operations = 0
11      
12        # The variable `current_sum` is used to store the running sum of numbers from the array
13        current_sum = 0
14      
15        # Iterate through each number in the list
16        for number in nums:
17            # Update the running sum
18            current_sum += number
19          
20            # If the number is negative, add it to the min-heap
21            if number < 0:
22                heappush(min_heap, number)
23          
24            # If current_sum drops below zero, we need to perform operations to make it non-negative
25            while current_sum < 0:
26                # The operation involves removing the smallest element (top of the min-heap) from the running sum
27                current_sum -= heappop(min_heap)
28              
29                # Increment the count of operations needed
30                total_operations += 1
31      
32        # Return the total number of operations performed to ensure all prefix sums are non-negative
33        return total_operations
34
1class Solution {
2    public int makePrefSumNonNegative(int[] nums) {
3        // A priority queue to store negative numbers, it will heapify them based on their natural order, i.e., the smallest number will be on top.
4        PriorityQueue<Integer> negativeNumbers = new PriorityQueue<>();
5      
6        // 'operations' will hold the count of the number of negative numbers removed from the prefix sum to make it non-negative.
7        int operations = 0;
8      
9        // 'sum' is used to store the running prefix sum of the array.
10        long sum = 0;
11      
12        // Iterate over each number in the array.
13        for (int number : nums) {
14            // Add the current number to the prefix sum.
15            sum += number;
16          
17            // If the number is negative, add it to the priority queue.
18            if (number < 0) {
19                negativeNumbers.offer(number);
20            }
21          
22            // If the prefix sum is negative, we need to perform operations.
23            while (sum < 0) {
24                // Remove the smallest negative number from the prefix sum to try and make it non-negative.
25                sum -= negativeNumbers.poll();
26              
27                // Increment the count of operations.
28                ++operations;
29            }
30        }
31      
32        // Return the total number of operations performed to make the prefix sum non-negative.
33        return operations;
34    }
35}
36
1class Solution {
2public:
3    int makePrefSumNonNegative(vector<int>& nums) {
4        // Initialize a min-heap to keep track of negative numbers
5        priority_queue<int, vector<int>, greater<int>> minHeap;
6      
7        int operations = 0; // Count the number of operations needed
8        long long prefixSum = 0; // This will store the prefix sum of the array
9      
10        // Iterate through the vector of numbers
11        for (int& num : nums) {
12            prefixSum += num; // Add current number to the prefix sum
13          
14            // If the number is negative, add it to the min-heap
15            if (num < 0) {
16                minHeap.push(num);
17            }
18          
19            // If the prefix sum is negative, we need to make operations
20            while (prefixSum < 0) {
21                // Remove the smallest negative number from prefix sum and from the min-heap
22                prefixSum -= minHeap.top();
23                minHeap.pop();
24              
25                // Increment the operation count as we removed one element
26                ++operations;
27            }
28        }
29      
30        // Return the total number of operations performed
31        return operations;
32    }
33};
34
1import { MinPriorityQueue } from '@datastructures-js/priority-queue'; // Make sure to import the priority queue data structure
2
3// This function adjusts the input array `nums` in such a way that the prefix sum never goes negative.
4// If necessary, it removes the smallest elements until the sum is non-negative.
5// It returns the number of elements removed to achieve this.
6function makePrefSumNonNegative(nums: number[]): number {
7    const priorityQueue = new MinPriorityQueue<number>(); // Initialize a minimum priority queue for numbers
8    let removals = 0; // Counter for the number of removed elements
9    let sum = 0; // Sum of elements encountered so far
10
11    // Iterate through each element in the `nums` array
12    for (const num of nums) {
13        sum += num; // Add current element to the sum
14        // If current element is negative, add it to the priority queue
15        if (num < 0) {
16            priorityQueue.enqueue(num);
17        }
18        // While the sum is negative, remove the smallest element from the priority queue to increase the sum
19        while (sum < 0) {
20            sum -= priorityQueue.dequeue().element; // Subtract the smallest element from sum
21            removals++; // Increment the removal counter
22        }
23    }
24
25    return removals; // Return the total number of elements removed
26}
27

Time and Space Complexity

The time complexity of the given code is O(n * log n). This is because the function iterates through all n elements of the input list nums. For each negative number encountered, it performs a heappush operation which is O(log k), where k is the number of negative numbers encountered so far, leading to a maximum of O(log n) when all elements are negative. Additionally, when the sum s becomes negative, the code performs a heappop in a while loop until s is non-negative again. In the worst case, this could involve popping every number that was pushed, resulting in a sequence of heappop operations. Since each heappop operation is O(log k), and you could theoretically pop every element once, the total time for all the heap operations across the entire list will be O(n * log n).

The space complexity of the given code is O(n). This is due to the additional heap h that is used to store the negative numbers. In the worst-case scenario, all elements in the list are negative and will be added to the heap. Since the heap can contain all negative numbers of the list at once, the space required for the heap is proportional to the input size, hence the space complexity is O(n).

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following uses divide and conquer strategy?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More