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

Minimum Positive Sum Subarray

Number: 3644

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

You are given an integer array nums and two integers l and r. The task is to find the minimum sum of a subarray whose size is between l and r (inclusive) and whose sum is greater than 0. If no such subarray exists, return -1.

Key Insights

  • Use a prefix sum array to compute the sum of any subarray quickly in O(1) time.
  • Since the maximum length of nums is 100, iterating over all possible subarrays with lengths between l and r is efficient.
  • Carefully consider cases where subarrays do not produce a positive sum; maintain the smallest valid sum found.
  • Return -1 if no positive-sum subarray exists.

Space and Time Complexity

Time Complexity: O(n²), where n is the length of nums, because we try all subarrays with lengths from l to r. Space Complexity: O(n) due to the prefix sum array.

Solution

The solution first builds a prefix sum array where each element prefix[i+1] represents the sum of nums[0...i]. For every possible starting index in nums, we consider all subarray lengths between l and r. The sum for each subarray is computed using the difference of the appropriate prefix sums. We compare the subarray sum if it's greater than 0 to determine if it is the minimum positive sum. If none is found, we return -1.

Code Solutions

# Python solution with line-by-line comments
def min_positive_sum_subarray(nums, l, r):
    n = len(nums)
    # Build prefix sum array with an extra element at the beginning.
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    
    # Initialize the result to infinity.
    min_sum = float("inf")
    # Iterate over every possible starting index.
    for start in range(n):
        # Evaluate each subarray length within the range [l, r].
        for length in range(l, r + 1):
            end = start + length
            # If the subarray exceeds the bounds, break out.
            if end > n:
                break
            current_sum = prefix[end] - prefix[start]
            # Check for positive sum and update the minimum.
            if current_sum > 0:
                min_sum = min(min_sum, current_sum)
    
    # Return the minimum positive sum found or -1 if none exists.
    return min_sum if min_sum != float("inf") else -1

# Example usage:
print(min_positive_sum_subarray([3, -2, 1, 4], 2, 3))  # Expected Output: 1
← Back to All Questions