LeetCode Problem 3511

Difficulty: 🟡 Medium
Topics: Array, Greedy, Prefix Sum

Solution

Before diving into the detailed solution guide, I want to clarify one subtle point: the problem specifies that all subarrays with more than two elements must have a positive sum. This means the smallest subarray we need to consider is of length 3. This nuance is crucial for correctness.

Here’s the comprehensive solution guide following your formatting rules.

Problem Understanding

The problem gives us an integer array nums and defines an array as positive if the sum of every subarray containing three or more elements is positive. We are allowed to change any element in the array to any integer between -10^18 and 10^18. The goal is to compute the minimum number of changes required to make the array positive.

In other words, we must ensure that every contiguous sequence of length 3 or more has a sum greater than zero. The input array length can go up to 10^5, and element values can be as large as 10^9 in magnitude. This indicates that a brute-force approach iterating through all subarrays would be computationally infeasible because the number of subarrays of length ≥ 3 is O(n^2).

Important edge cases include arrays that are already positive, arrays where only one element dominates negative subarray sums, and arrays that contain the maximum or minimum integer values, which could stress integer handling.

Approaches

The brute-force approach would iterate through all subarrays of length ≥ 3, compute their sums, and track which elements need replacement to make the sum positive. While this is straightforward and guarantees correctness, it is prohibitively slow. Specifically, the number of subarrays is roughly n(n-1)/2 - n - 1, which is O(n^2).

The key insight for an optimal solution is that we do not need to check every subarray individually. The constraint that all subarrays of length ≥ 3 must have positive sum implies that if we enforce positivity for subarrays of length 3 only, then all larger subarrays composed of overlapping length-3 subarrays will also have positive sum if the middle element is adjusted optimally. This allows a greedy approach, replacing elements as needed from left to right, using prefix sums to track the cumulative effect of replacements efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check every subarray of length ≥ 3 and count necessary replacements
Optimal	O(n)	O(1)	Greedy scan, replace elements to maintain positive rolling sum of length 3 subarrays

Algorithm Walkthrough

1. Initialize a counter operations = 0 to track the number of replacements performed.
2. Iterate through the array starting from the first element. Maintain a rolling sum of the last two elements to check each length-3 subarray ending at the current index.
3. For each element nums[i] where i >= 2, compute the sum of the subarray [nums[i-2], nums[i-1], nums[i]].
4. If this sum is positive, no action is needed, and the rolling sum is updated to include nums[i].
5. If the sum is zero or negative, compute the minimum replacement needed to make the sum positive. Update nums[i] accordingly, increment operations, and update the rolling sum with the new value.
6. Continue this process to the end of the array, ensuring that all length-3 subarrays have positive sums.

Why it works: The algorithm works because by enforcing positivity on every consecutive subarray of length 3, we automatically guarantee that any larger subarray formed from these overlapping triples will also have a positive sum. Adjusting the last element in each negative sum subarray ensures the minimal number of replacements.

Problem Understanding

The problem defines a “positive array” using a somewhat global condition over all subarrays of length at least three. Concretely, an array is considered valid if every contiguous subarray whose length is greater than two has a strictly positive sum.

You are allowed to modify the array by repeatedly choosing a single index and replacing its value with any integer in the range $[-10^{18}, 10^{18}]$. Each such replacement counts as one operation, and the goal is to minimize the number of operations required to make the array satisfy the positivity condition for all subarrays of length at least three.

The input is a single integer array nums, and the output is the minimum number of modifications needed so that every subarray of length three or more has a positive sum.

The constraints indicate that the array can be quite large, up to $10^5$ elements, and values can be very large in magnitude. This immediately implies that any solution with quadratic or cubic behavior over subarrays is infeasible. The solution must operate in linear or near-linear time.

The most important edge cases arise when the array is already valid, when it is highly alternating between large negative and positive values, or when violations are concentrated in overlapping subarrays so that a single modification can fix multiple constraints at once. Another key observation is that because we can assign arbitrarily large values, a single modification can “repair” multiple subarrays simultaneously if chosen strategically.

Approaches

A brute-force approach would explicitly check every subarray of length at least three, compute its sum, and attempt all possible ways of modifying elements to fix violations. Even if we only check validity without modifications, there are $O(n^2)$ subarrays, and each sum computation takes $O(1)$ with prefix sums, leading to $O(n^2)$ time. Once we introduce modifications, the state space becomes exponential because each element can be modified or not, and each modification can take many values.

The key insight is that we do not actually need to reason about all subarrays directly. Instead, we transform the condition into a local constraint using prefix sums. A subarray sum condition can be rewritten as a relationship between prefix sums:

For any subarray $[l, r]$ with $r - l + 1 \ge 3$,

$$prefix[r] - prefix[l-1] > 0 \Rightarrow prefix[r] > prefix[l-1]$$

This means that any two prefix values separated by at least three indices must be strictly increasing. Therefore, each prefix value must be greater than the minimum prefix value that occurred at least three positions before it.

This reduces the problem into maintaining a constrained monotonic property over a sliding window of prefix differences. Violations can be detected locally, and each modification can be interpreted as a “repair” that enforces a strong positive jump in the prefix structure, eliminating multiple future violations.

Comparison of approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force over subarrays and modifications	Exponential	O(n) to O(n²)	Tries all modifications and checks all subarrays, infeasible
Prefix constraint greedy optimization	O(n)	O(n) or O(1)	Uses prefix relationships and fixes violations greedily

Algorithm Walkthrough

The optimal strategy is based on scanning the array while maintaining prefix sums and ensuring the prefix constraint over distance three is never violated.

Step-by-step process

1. Compute prefix sums implicitly while iterating through the array. Instead of storing all prefix values explicitly, maintain a running prefix sum.
2. Maintain a sliding structure that tracks the minimum prefix value among indices that are at least three positions behind the current index. This represents the constraint baseline for validity.
3. At each index i, compare the current prefix sum with the minimum prefix sum from indices i - 3 and earlier. If the current prefix is not strictly greater, a violation exists, meaning there is at least one subarray ending at i (with length ≥ 3) whose sum is non-positive.
4. When a violation is detected, we must perform an operation. The optimal greedy decision is to “fix” the current region by modifying the current element so that it becomes sufficiently large and positive, forcing the prefix sum to jump above all previous problematic values.
5. After performing a modification at index i, we conceptually reset the local constraint influence for the next few elements, because any subarray involving the modified element can now be made valid due to the ability to assign arbitrarily large values.
6. Continue scanning forward, applying the same rule, ensuring that each modification is only performed when absolutely necessary.

Why it works

The core invariant is that the algorithm maintains validity of all subarrays ending sufficiently far behind the current index. Any violation detected at index i corresponds to a minimal “breaking point” in the prefix ordering constraint. Because a single modification can arbitrarily increase one prefix value, it is always optimal to fix the earliest detected violation rather than delaying it. This greedy choice ensures that each operation eliminates as many future invalid subarrays as possible, preventing redundant modifications.

Python Solution

from typing import List

class Solution:
    def makeArrayPositive(self, nums: List[int]) -> int:
        operations = 0
        n = len(nums)
        
        # Iterate from the third element
        for i in range(2, n):
            current_sum = nums[i-2] + nums[i-1] + nums[i]
            if current_sum <= 0:
                # Minimum replacement needed to make sum positive
                diff = 1 - current_sum
                nums[i] += diff
                operations += 1
        return operations

Implementation walkthrough: We loop starting from index 2 because that is the first subarray of length 3. For each subarray, we calculate the sum. If the sum is already positive, we continue. Otherwise, we calculate the difference required to make the sum at least 1 and add it to the current element. This guarantees minimal changes because we always adjust the last element of the problematic subarray. n = len(nums)

    # prefix sum as we iterate
    prefix = 0
    
    # we maintain prefix history in a list
    # for simplicity; in optimized version this can be replaced with deque/min structure
    pref = [0]
    
    operations = 0
    
    for i in range(n):
        prefix += nums[i]
        pref.append(prefix)
        
        # only start checking when we have i >= 2 (subarray length >= 3)
        if i >= 2:
            # compute min prefix up to i-2 (i-3 in 0-based prefix index space)
            min_prev = min(pref[:i-1])  # prefix indices up to i-2
            
            # violation: prefix[i+1] <= min prefix before i-2
            if pref[-1] <= min_prev:
                operations += 1
                
                # simulate fixing: set current element very large positive
                # so prefix becomes large enough to dominate
                pref[-1] = min_prev + 1
                prefix = pref[-1]
    
    return operations

### Explanation of the code

The implementation maintains a running prefix sum while also storing historical prefix values. At each index, once we reach a position where subarrays of length at least three are possible, we compare the current prefix against the minimum prefix from the valid historical window.

If a violation is detected, we count one operation and simulate a correction by forcing the current prefix to exceed the historical minimum. This models the effect of replacing the current element with a very large value.

Although this version uses a simple minimum computation for clarity, the optimal version would maintain a sliding minimum structure to ensure linear time complexity.

## Go Solution

```go
func makeArrayPositive(nums []int) int {
    operations := 0
    n := len(nums)

    for i := 2; i < n; i++ {
        currentSum := nums[i-2] + nums[i-1] + nums[i]
        if currentSum <= 0 {
            diff := 1 - currentSum
            nums[i] += diff
            operations++
        }
    }
    return operations
}

Go-specific notes: We use slices and index access similar to Python. Since Go integers are 64-bit by default, this safely handles the large values allowed in the problem constraints. We increment the counter and adjust nums[i] directly, just like in Python.

Worked Examples

Example 1: nums = [-10, 15, -12]

i	Subarray	Sum	Action	nums after action	operations
2	[-10, 15, -12]	-7	Replace nums[2] by adding 8	[-10, 15, -4]	1

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

i	Subarray	Sum	Action	nums after action	operations
2	[-1, -2, 3]	0	Replace nums[2] by +1	[-1, -2, 4, -1, 2, 6]	1
3	[-2, 4, -1]	1	Already positive	-	1
4	[4, -1, 2]	5	Already positive	-	1
5	[-1, 2, 6]	7	Already positive	-	1

Example 3: nums = [1,2,3]

All subarrays have positive sums, no operations needed. package main

func makeArrayPositive(nums []int) int { n := len(nums)

prefix := 0
pref := make([]int, 0, n+1)
pref = append(pref, 0)

operations := 0

for i := 0; i < n; i++ {
	prefix += nums[i]
	pref = append(pref, prefix)

	if i >= 2 {
		minPrev := pref[0]
		for j := 1; j <= i-1; j++ {
			if pref[j] < minPrev {
				minPrev = pref[j]
			}
		}

		if pref[len(pref)-1] <= minPrev {
			operations++
			pref[len(pref)-1] = minPrev + 1
			prefix = pref[len(pref)-1]
		}
	}
}

return operations

}

### Go-specific notes

The Go version mirrors the Python logic closely but uses slices instead of dynamic lists. Because Go does not have built-in functional constructs for prefix minima, the implementation explicitly scans the prefix slice when needed. In a production-optimized version, this would be replaced with a monotonic deque or segment structure to maintain linear time complexity.

## Worked Examples

### Example 1: nums = [-10, 15, -12]

We track prefix sums:

| i | nums[i] | prefix | min prefix (i-3 constraint) | action |
| --- | --- | --- | --- | --- |
| 0 | -10 | -10 | N/A | no check |
| 1 | 15 | 5 | N/A | no check |
| 2 | -12 | -7 | 0 | violation detected |

At i = 2, prefix is -7 which is not greater than previous minimum prefix (0). We perform 1 modification and force prefix to become positive, for example 3.

Final answer is 1.

### Example 2: nums = [-1, -2, 3, -1, 2, 6]

| i | prefix | min prev (i-3) | violation |
| --- | --- | --- | --- |
| 0 | -1 | - | no |
| 1 | -3 | - | no |
| 2 | 0 | 0 | yes |
| 3 | -1 | -1 | yes but resolved by prior fix |
| 4 | 1 | -1 | no |
| 5 | 7 | -1 | no |

Only one correction is needed at the first major violation point, and it propagates forward to fix later inconsistencies.

### Example 3: nums = [1, 2, 3]

All prefix sums are strictly increasing, and no violation is ever triggered. The algorithm performs zero operations.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Each element is visited once, and subarray sum is computed in O(1) using rolling sum logic |
| Space | O(1) | No extra data structures are used, modifications are in-place |

The algorithm is efficient because it only makes a single pass through the array and performs constant-time operations for each element.
| Time | O(n) amortized (O(n²) in naive form) | Each element is processed once; each violation is handled greedily |
| Space | O(n) | Prefix storage in the straightforward implementation |

The optimized solution relies on maintaining a rolling minimum over a sliding window, reducing prefix minimum queries to O(1), which yields true linear time complexity.

## Test Cases

Provided examples

assert Solution().makeArrayPositive([-10, 15, -12]) == 1 # minimal replacement assert Solution().makeArrayPositive([-1, -2, 3, -1, 2, 6]) == 1 # overlapping subarrays assert Solution().makeArrayPositive([1, 2, 3]) == 0 # already positive

Edge cases

assert Solution().makeArrayPositive([-109, -109, -109]) == 1 # large negatives assert Solution().makeArrayPositive([0, 0, 0]) == 1 # zeros assert Solution().makeArrayPositive([1, -1, 1, -1, 1, -1]) == 2 # alternating signs assert Solution().makeArrayPositive([109, -10**9, 0]) == 1 # mix large numbers assert Solution().makeArrayPositive([-10, 15, -12]) == 1 # basic single fix case assert Solution().makeArrayPositive([-1, -2, 3, -1, 2, 6]) == 1 # overlapping subarrays assert Solution().makeArrayPositive([1, 2, 3]) == 0 # already valid assert Solution().makeArrayPositive([-1, -1, -1]) == 1 # all negative assert Solution().makeArrayPositive([5, -100, 5, -100, 5]) == 2 # alternating extreme values assert Solution().makeArrayPositive([10, -1, -1, -1, 10]) == 1 # boundary dominance case

| Test | Why |
| --- | --- |
| [-10, 15, -12] | Minimal negative sum requires one replacement |
| [-1, -2, 3, -1, 2, 6] | Overlapping subarrays, only one replacement needed |
| [1,2,3] | Already positive, no changes |
| [-10^9, -10^9, -10^9] | Large negatives test integer handling |
| [0,0,0] | Zero sum requires positive adjustment |
| [1,-1,1,-1,1,-1] | Alternating signs stress the greedy adjustment |
| [10^9,-10^9,0] | Mix of large positives and negatives |

## Edge Cases

**Edge Case 1: All zeros**

A subarray of length 3 with all zeros has sum zero. The algorithm correctly adds 1 to the last element of the first subarray to make it positive.

**Edge Case 2: Large negative numbers**

Subarrays with very large negative values could cause overflow in some languages. Python handles this automatically, and Go’s `int64` is sufficient.

**Edge Case 3: Already positive array**

Arrays that satisfy the positivity condition initially should return 0. The algorithm correctly checks sub
| `[-10, 15, -12]` | minimal case requiring one correction |
| `[-1, -2, 3, -1, 2, 6]` | overlapping subarray constraint propagation |
| `[1, 2, 3]` | already valid array |
| `[-1, -1, -1]` | uniform negative stress case |
| `[5, -100, 5, -100, 5]` | alternating extreme values |
| `[10, -1, -1, -1, 10]` | single strong anchor fixes multiple violations |

## Edge Cases

One important edge case is when the array is already strictly increasing in prefix sums. In this situation, no subarray of length three or more can have a non-positive sum, so the algorithm must correctly return zero operations without triggering any unnecessary corrections.

Another edge case occurs when the array contains extremely large negative values clustered together. In such cases, multiple overlapping subarrays violate the condition simultaneously. The greedy approach ensures that a single modification within the cluster resolves multiple violations at once, avoiding redundant operations.

A final edge case is when violations are sparse but strategically spaced so that fixing one affects distant subarrays. The prefix-based invariant ensures that each correction is only made when a true global violation is detected, and because modifications can be arbitrarily large, each operation is maximally impactful, preventing cascading under-corrections.