Minimum Positive Sum Subarray

Difficulty: Easy | Acceptance: 45.00% | Paid: No Topics: Array, Sliding Window, Prefix Sum

You are given an integer array nums. Return the minimum sum of a non-empty subarray of nums that is strictly positive. If no such subarray exists, return -1.

A subarray is a contiguous non-empty sequence of elements within the array.

• Examples
• Constraints
• Brute Force
• Sliding Window
• Prefix Sum

Examples

Example 1:

Input: nums = [3, -2, 1, 4, -5]
Output: 1
Explanation: The subarray [1] has the minimum positive sum of 1.

Example 2:

Input: nums = [-2, -3, -1]
Output: -1
Explanation: There is no subarray with a positive sum.

Example 3:

Input: nums = [5, 4, -10, 2]
Output: 1
Explanation: The subarray [5, 4, -10, 2] has a sum of 1, which is the minimum positive sum.

Constraints

1 <= nums.length <= 50
-1000 <= nums[i] <= 1000

Brute Force

Intuition We can iterate through every possible starting index of the subarray. For each starting index, we expand the subarray to the right, calculating the running sum. If the running sum becomes positive, we check if it is the smallest positive sum found so far.

Steps

• Initialize min_sum to infinity.
• Iterate i from 0 to n-1 (start index).
• Initialize current_sum to 0.
• Iterate j from i to n-1 (end index).
• Add nums[j] to current_sum.
• If current_sum is greater than 0 and less than min_sum, update min_sum.
• After loops, if min_sum is still infinity, return -1. Otherwise, return min_sum.

class Solution:
    def minPositiveSumSubarray(self, nums: list[int]) -> int:
        n = len(nums)
        min_sum = float('inf')
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                if current_sum > 0 and current_sum < min_sum:
                    min_sum = current_sum
        return -1 if min_sum == float('inf') else min_sum

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple to implement and efficient enough given the constraint n <= 50.

Sliding Window

Intuition We can iterate through all possible window sizes k from 1 to n. For each fixed window size k, we use the sliding window technique to calculate the sum of every subarray of length k in O(n) time. We track the minimum positive sum encountered across all window sizes.

Steps

• Initialize min_sum to infinity.
• Iterate k from 1 to n (window size).
• Calculate the sum of the first window of size k.
• If this sum is positive, update min_sum.
• Slide the window from index 1 to n - k:
  • Subtract the element leaving the window and add the new element entering.
  • If the new sum is positive and smaller than min_sum, update min_sum.
• Return min_sum (or -1 if unchanged).

class Solution:
    def minPositiveSumSubarray(self, nums: list[int]) -> int:
        n = len(nums)
        min_sum = float('inf')
        
        for k in range(1, n + 1):
            window_sum = sum(nums[:k])
            if window_sum > 0:
                min_sum = min(min_sum, window_sum)
            
            for i in range(1, n - k + 1):
                window_sum = window_sum - nums[i - 1] + nums[i + k - 1]
                if window_sum > 0:
                    min_sum = min(min_sum, window_sum)
                    
        return -1 if min_sum == float('inf') else min_sum

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Also O(n²) time, but conceptually distinct by iterating over window sizes first.

Prefix Sum

Intuition We can precompute prefix sums where prefix[i] is the sum of the first i elements. The sum of any subarray from index i to j-1 is prefix[j] - prefix[i]. We iterate through all pairs (i, j) to find the minimum positive difference.

Steps

• Create a prefix array of size n+1, initialized with 0.
• Fill prefix such that prefix[i] = prefix[i-1] + nums[i-1].
• Iterate i from 0 to n-1.
• Iterate j from i+1 to n.
• Calculate current_sum = prefix[j] - prefix[i].
• If current_sum > 0 and current_sum < min_sum, update min_sum.
• Return result.

class Solution:
    def minPositiveSumSubarray(self, nums: list[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + nums[i - 1]
        
        min_sum = float('inf')
        for i in range(n):
            for j in range(i + 1, n + 1):
                current_sum = prefix[j] - prefix[i]
                if current_sum > 0 and current_sum < min_sum:
                    min_sum = current_sum
                    
        return -1 if min_sum == float('inf') else min_sum

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Uses extra space for the prefix array, but allows O(1) sum calculation for any subarray.