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:
nums with any integer between -1018 and 1018.Find the minimum number of operations needed to make nums positive.
Example 1:
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:
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:
Input: nums = [1,2,3]
Output: 0
Explanation:
The array is already positive, so no operations are needed.
Constraints:
3 <= nums.length <= 105-109 <= nums[i] <= 109Problem Overview: You are given an integer array and need to ensure every prefix sum of the array remains strictly positive. The task typically allows modifying elements (such as flipping negative values) while minimizing the number of operations. The core challenge is maintaining a running prefix sum that never drops to zero or below.
Approach 1: Brute Force Prefix Fixing (O(n^2) time, O(1) space)
Compute the prefix sum while scanning the array. Whenever the running sum becomes non‑positive, look backward and choose a negative element to flip or adjust so the prefix becomes positive again. Each time the prefix fails, you may need to scan previously processed elements to decide which one to modify. This works conceptually but becomes expensive because every prefix violation may trigger another linear scan. Time complexity grows to O(n^2) with constant extra space.
Approach 2: Greedy with Prefix Sum and Max Heap (O(n log n) time, O(n) space)
Track a running prefix sum while iterating through the array. Every time you encounter a negative value, push it into a max heap (or priority queue). The key greedy insight: if the prefix sum becomes non‑positive, flipping the most negative element seen so far increases the prefix sum the most. Pop the largest‑magnitude negative value from the heap and flip it, which effectively adds twice its absolute value to the prefix sum. Continue until the prefix becomes positive again. Each element is inserted and possibly removed from the heap once, giving O(n log n) time and O(n) space.
This method relies on maintaining the running total via prefix sum while using a priority queue to enforce the greedy choice. The heap ensures the correction step always picks the modification that maximally restores the prefix balance.
Recommended for interviews: The greedy heap approach is what interviewers expect. Starting with the brute force explanation shows you understand the prefix constraint, but the optimized solution demonstrates knowledge of greedy algorithms and efficient data structures applied to array processing. The key observation is that fixing the most negative value gives the largest prefix increase, which makes the greedy choice provably optimal.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Fixing | O(n^2) | O(1) | Useful for reasoning about the problem and validating small inputs |
| Greedy + Max Heap with Prefix Sum | O(n log n) | O(n) | General optimal solution when array contains both positive and negative values |
Practice Make a Positive Array with our built-in code editor and test cases.
Practice on FleetCode