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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make a Positive Array

Number: 3855

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an integer array nums, you are allowed to perform an operation that replaces a single element with any integer (in the range [–10^18, 10^18]). An array is defined as positive if every contiguous subarray with more than two elements (that is, every subarray of length ≥ 3) has a strictly positive sum. Determine the minimum number of operations required to make the array positive.

Key Insights

  • Any subarray of length ≥ 3 that has a non‐positive sum is “bad” and must be “fixed” by having at least one element replaced (so that we can assign it a huge positive value).
  • Since a replacement can be chosen arbitrarily large, it “fixes” every subarray that covers the replaced index.
  • It turns out that one can show that if there is any “bad” contiguous subarray (of length ≥ 3), then at least one of its “small” windows – a window of three or four consecutive elements – must have non‐positive sum.
  • Thus we “cover” all violations by checking every triple (consecutive 3 elements) and every quadruple (consecutive 4 elements).
  • The problem then reduces to an “interval hitting set” problem: Each bad triple or quadruple defines an interval (its indices) and we want to choose as few indices (operations) as possible so that every interval is “hit” by at least one replacement.

Space and Time Complexity

Time Complexity: O(n log n) (due to sorting the “bad” intervals)
Space Complexity: O(n)

Solution

The solution uses the following strategy:

  1. Scan through nums to identify all “bad” intervals. In this context, we check: • Every triple (i, i+1, i+2) – if the sum is ≤ 0 then record the interval [i, i+2].
    • Every quadruple (i, i+1, i+2, i+3) – if the sum is ≤ 0 then record the interval [i, i+3].
  2. By a (non‐trivial) observation it is sufficient to “fix” these small intervals; any violation among longer subarrays will include at least one triple or quadruple whose sum isn’t positive.
  3. Once all intervals are collected, we use a greedy algorithm for the minimum hitting set: sort the intervals by their right endpoint (end index) and then choose the rightmost point of the first uncovered interval as a “replacement index”. This operation “covers” every interval that contains that index.
  4. Setting the chosen index’s value to a very large integer will “fix” all intervals intersecting it.
  5. The minimum number of replacement operations is the size of this hitting set.

Code Solutions

# Python solution for Make a Positive Array

def makePositiveArray(nums):
    n = len(nums)
    intervals = []  # list to hold intervals (start, end) for every bad window
    
    # Check every contiguous triple, i.e. indices [i, i+2]
    for i in range(n - 2):
        triple_sum = nums[i] + nums[i+1] + nums[i+2]
        if triple_sum <= 0:
            intervals.append((i, i+2))
            
    # Check every contiguous quadruple, i.e. indices [i, i+3]
    for i in range(n - 3):
        quad_sum = nums[i] + nums[i+1] + nums[i+2] + nums[i+3]
        if quad_sum <= 0:
            intervals.append((i, i+3))
            
    # If no bad interval is found, the array is already positive.
    if not intervals:
        return 0

    # Greedy interval covering: sort intervals by their end index.
    intervals.sort(key=lambda interval: interval[1])
    
    operations = 0  # count of replacements
    # current_cover is the index at which we did the last replacement
    current_cover = -1
    
    # Iterate over intervals; if the interval is not covered by current_cover, pick its end as a new replacement.
    for start, end in intervals:
        if start > current_cover:
            operations += 1
            current_cover = end  # choose the end index as the replacement index
    return operations

# Example usage:
#print(makePositiveArray([-10,15,-12])) # Expected output 1
#print(makePositiveArray([-1,-2,3,-1,2,6])) # Expected output 1
#print(makePositiveArray([1,2,3]))  # Expected output 0
← Back to All Questions