Skip to content

3511. Make a Positive Array πŸ”’

Description

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.

 

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] <= 109

Solutions

Solution 1

Thinking

Checking every subarray of length at least \(3\) is \(O(n^2)\), and \(n \le 10^5\). Replacing a value with an arbitrary integer cuts the prefix constraint at that index.

Scan prefix sums from the left, keeping the window start and \(\textit{pre\_mx}\), the maximum prefix sum of length at least \(2\) inside the window. If the current prefix is at most \(\textit{pre\_mx}\), a non-positive subarray appeared: count one replacement and reset the window. Cutting at the conflict minimizes operations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def makeArrayPositive(self, nums: List[int]) -> int:
        l = -1
        ans = pre_mx = s = 0
        for r, x in enumerate(nums):
            s += x
            if r - l > 2 and s <= pre_mx:
                ans += 1
                l = r
                pre_mx = s = 0
            elif r - l >= 2:
                pre_mx = max(pre_mx, s - x - nums[r - 1])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int makeArrayPositive(int[] nums) {
        int ans = 0;
        long preMx = 0, s = 0;
        for (int l = -1, r = 0; r < nums.length; r++) {
            int x = nums[r];
            s += x;
            if (r - l > 2 && s <= preMx) {
                ans++;
                l = r;
                preMx = s = 0;
            } else if (r - l >= 2) {
                preMx = Math.max(preMx, s - x - nums[r - 1]);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int makeArrayPositive(vector<int>& nums) {
        int ans = 0;
        long long preMx = 0, s = 0;
        for (int l = -1, r = 0; r < nums.size(); r++) {
            int x = nums[r];
            s += x;
            if (r - l > 2 && s <= preMx) {
                ans++;
                l = r;
                preMx = s = 0;
            } else if (r - l >= 2) {
                preMx = max(preMx, s - x - nums[r - 1]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func makeArrayPositive(nums []int) (ans int) {
    l := -1
    preMx := 0
    s := 0
    for r, x := range nums {
        s += x
        if r-l > 2 && s <= preMx {
            ans++
            l = r
            preMx = 0
            s = 0
        } else if r-l >= 2 {
            preMx = max(preMx, s-x-nums[r-1])
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function makeArrayPositive(nums: number[]): number {
    let l = -1;
    let [ans, preMx, s] = [0, 0, 0];
    for (let r = 0; r < nums.length; r++) {
        const x = nums[r];
        s += x;
        if (r - l > 2 && s <= preMx) {
            ans++;
            l = r;
            preMx = 0;
            s = 0;
        } else if (r - l >= 2) {
            preMx = Math.max(preMx, s - x - nums[r - 1]);
        }
    }
    return ans;
}

Comments