Problem

You are given an array nums. An array is considered positive if the sum of all numbers in each subarray with more than two elements is positive.

You can perform the following operation any number of times:

  • Replace one element in nums with any integer between -1018 and 1018.

Find the minimum number of operations needed to make nums positive.

Examples

Example 1

1
2
3
4
5
6
7

Input: nums = [-10,15,-12]

Output: 1

Explanation:

The only subarray with more than 2 elements is the array itself. The sum of all elements is (-10) + 15 + (-12) = -7. By replacing nums[0] with 0, the new sum becomes 0 + 15 + (-12) = 3. Thus, the array is now positive.

Example 2

1
2
3
4
5
6
7

Input: nums = [-1,-2,3,-1,2,6]

Output: 1

Explanation:

The only subarrays with more than 2 elements and a non-positive sum are:
Subarray Indices Subarray Sum Subarray After Replacement (Set nums[1] = 1) New Sum
nums[0...2] [-1, -2, 3] 0 [-1, 1, 3] 3
nums[0...3] [-1, -2, 3, -1] -1 [-1, 1, 3, -1] 2
nums[1...3] [-2, 3, -1] 0 [1, 3, -1] 3

Thus, nums is positive after one operation.

Example 3

1
2
3
4
5
6
7

Input: nums = [1,2,3]

Output: 0

Explanation:

The array is already positive, so no operations are needed.

Constraints

  • 3 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Solution

Method 1 – Greedy with Prefix Sum

Intuition

To make all prefix sums of the array positive with the minimum number of sign flips, we can greedily flip the most negative numbers encountered so far whenever the prefix sum becomes non-positive. Using a min-heap allows us to efficiently track and flip the largest negative numbers in the prefix.

Approach

  1. Initialize a prefix sum variable and a min-heap to store negative numbers in the prefix.
  2. Iterate through the array, updating the prefix sum.
  3. If the prefix sum becomes non-positive, pop the largest negative number from the heap (i.e., flip its sign), increment the flip count, and update the prefix sum accordingly.
  4. Continue until the end of the array.
  5. Return the minimum number of flips needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <queue>
class Solution {
public:
    int makePrefSumPositive(vector<int>& nums) {
        int flips = 0, pre = 0;
        priority_queue<int> pq;
        for (int x : nums) {
            pre += x;
            if (x < 0) pq.push(-x);
            while (pre <= 0 && !pq.empty()) {
                pre += 2 * pq.top();
                pq.pop();
                flips++;
            }
        }
        return flips;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import java.util.*;
class Solution {
    public int makePrefSumPositive(int[] nums) {
        int flips = 0, pre = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) {
            pre += x;
            if (x < 0) pq.offer(x);
            while (pre <= 0 && !pq.isEmpty()) {
                int neg = pq.poll();
                pre += -2 * neg;
                flips++;
            }
        }
        return flips;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import heapq
class Solution:
    def makePrefSumPositive(self, nums: list[int]) -> int:
        flips = 0
        pre = 0
        heap = []
        for x in nums:
            pre += x
            if x < 0:
                heapq.heappush(heap, x)
            while pre <= 0 and heap:
                neg = heapq.heappop(heap)
                pre += -2 * neg
                flips += 1
        return flips

Complexity

  • ⏰ Time complexity: O(n log n), as each negative number may be pushed and popped from the heap.
  • 🧺 Space complexity: O(n), for the heap storing negative numbers.