We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make the Prefix Sum Non-negative

Number: 2674

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a 0-indexed integer array nums, you are allowed to perform the following operation any number of times: Pick any element from nums and move it to the end of the array. The goal is to achieve a configuration such that the prefix sum array (where prefix[i] is the sum of nums[0] through nums[i]) contains no negative numbers. It is guaranteed that it is always possible to make the prefix sum non-negative. Return the minimum number of operations required.

Key Insights

  • The only operation allowed is to take an element from anywhere in the array and append it to the end.
  • The effect of moving an element is equivalent to “removing” its contribution from the prefix part of the array.
  • If the current prefix sum becomes negative, one must “remove” (i.e., postpone) one of the previously encountered negative contributions.
  • A greedy strategy is used: when the prefix sum is negative, remove the element with the largest negative effect (i.e. the most negative number) from the prefix.
  • A max-heap (priority queue) is ideal to quickly retrieve the element with the worst (most negative) contribution.

Space and Time Complexity

Time Complexity: O(n log n), where n is the length of nums. Each element is processed once and may be added/removed from the heap. Space Complexity: O(n), for storing negative elements in the heap.

Solution

We iterate through the array while maintaining the current prefix sum. For each element, we add its value to the prefix sum. If the element is negative, push it into a max-heap (which is implemented by storing the value directly in languages where the default priority queue is a max-heap, or using a custom comparator). If at any point the prefix sum becomes negative, repeatedly remove the element with the largest negative effect from the heap (thus “postponing” it by simulating its removal from the current prefix) until the prefix sum is non-negative. Each removal is counted as an operation. This greedy removal ensures that with the minimum number of moves, the prefix sum is adjusted back to non-negative.

Code Solutions

import heapq

class Solution:
    def makeNonNegativePrefixSum(self, nums):
        prefix_sum = 0  # current prefix sum
        ops = 0       # count of operations (moves)
        max_heap = [] # will store negative numbers; Python heapq is a min-heap so we push the actual negatives
        
        for num in nums:
            prefix_sum += num
            # If the element is negative, push it into our heap
            if num < 0:
                heapq.heappush(max_heap, num)
            # If the prefix sum goes negative, remove the worst (most negative) contribution
            while prefix_sum < 0 and max_heap:
                worst = heapq.heappop(max_heap)  # removes the smallest (most negative) value
                prefix_sum -= worst             # subtracting a negative value increases the prefix sum
                ops += 1
        return ops

# Test cases
if __name__ == "__main__":
    sol = Solution()
    print(sol.makeNonNegativePrefixSum([2, 3, -5, 4]))  # Expected output: 0
    print(sol.makeNonNegativePrefixSum([3, -5, -2, 6]))  # Expected output: 1
← Back to All Questions