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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Positive Sum Subarray

Difficulty: Easy

Problem Description

You are given an integer array nums and two integers l and r. Your 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. Return the minimum sum of such a subarray. If no such subarray exists, return -1.

Key Insights

  • A subarray is a contiguous non-empty sequence of elements within an array.
  • The size of the subarray must be between l and r.
  • We need to find the minimum positive sum of these subarrays.
  • Sliding window technique can be useful to maintain a subarray of a specific length.
  • Prefix sums can help in quickly calculating sums of subarrays.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem, we can use a nested loop to evaluate all possible subarrays within the given bounds of l and r. The outer loop will iterate through the starting index of the subarray, while the inner loop will extend the subarray until it reaches a length of r. For each valid subarray, we check if its sum is greater than 0 and keep track of the minimum sum encountered. If no valid subarray is found by the end of the process, we return -1.

Code Solutions

def min_positive_sum_subarray(nums, l, r):
    min_sum = float('inf')  # Initialize min_sum to infinity
    n = len(nums)

    # Iterate over all possible starting points of the subarray
    for i in range(n):
        current_sum = 0
        
        # Extend the subarray to lengths between l and r
        for j in range(i, min(i + r, n)):
            current_sum += nums[j]
            # Only consider subarrays of size at least l
            if j - i + 1 >= l and current_sum > 0:
                min_sum = min(min_sum, current_sum)

    return min_sum if min_sum != float('inf') else -1
← Back to All Questions