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:
-
Initialize an empty min heap
h
, an accumulatorans
to count the number of moves, and a sums
to keep track of the prefix sum. -
Iterate over each element
x
in the arraynums
:- Add the current element to the prefix sum
s
(=s + x
). - If
x
is negative, push it onto the min heaph
usingheappush(h, x)
.
- Add the current element to the prefix sum
-
After each addition of an element to
s
, check ifs
is negative:- While
s
is negative, repeatedly:- Pop the smallest (most negative) element from the min heap
h
usingheappop(h)
. - Subtract the popped element from
s
, which will makes
less negative or non-negative. - Increment
ans
by 1 representing an operation.
- Pop the smallest (most negative) element from the min heap
- While
-
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 EvaluatorExample Walkthrough
Consider the following small example array nums
: [3, -7, 4, -2, 1, 2]
-
We initialize the following:
- Min heap
h
: [] - Operation counter
ans
: 0 - Prefix sum
s
: 0
- Min heap
-
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 fromh
(-7), add it back tos
(+7), and incrementans
by 1. s
is now 3 (-4 + 7), andans
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]
- For the first element (3):
-
Since we've finished processing
nums
ands
is non-negative,ans
remains at 1. -
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.
Which of the following uses divide and conquer strategy?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!