Minimum Positive Sum Subarray — Easy Problem & Solution

Problem statement

You are given an integer array nums and two integers l and r.

Among all contiguous subarrays whose length is between l and r (inclusive) and whose sum is strictly greater than 0, find the smallest sum.

Return that minimum sum, or -1 if no such subarray exists.

Example 1

Input: nums = [5,-3,2,-1], l = 2, r = 3
Output: 1
Explanation: The length-2 sums are 2, -1, 1 and the length-3 sums are 4, -2. The positive ones are 2, 1 and 4.

Example 2

Input: nums = [-4,1,-2], l = 2, r = 3
Output: -1
Explanation: Every subarray of length 2 or 3 has a negative sum.

Example 3

Input: nums = [2,2,2], l = 3, r = 3
Output: 6

Constraints

• 1 <= nums.length <= 100
• 1 <= l <= r <= nums.length
• -1000 <= nums[i] <= 1000

How to solve Minimum Positive Sum Subarray

Enumerate every subarray whose length lies in [l, r], computing sums with prefix sums (or a fixed-length sliding window per length), and keep the smallest positive one.

Approach

1. Build prefix sums P with P[0] = 0.
2. For each length len from l to r, and each start i with i + len <= n, compute s = P[i + len] - P[i].
3. If s > 0 and it is smaller than the best so far (or no best exists yet), record it.
4. Return the best, or -1 if nothing was recorded.

Why it works

Every subarray of an allowed length is examined exactly once, and the filter keeps precisely those with a positive sum, so the minimum over them is the answer by definition.

Complexity

• Time — O(n · (r - l + 1))
• Space — O(n)

Pitfalls

• A sum of exactly 0 is not positive and must be skipped.
• Start with "no answer" (-1) rather than 0, or a real answer may never replace it.
• Both length bounds are inclusive.

Reference solution

Python

from typing import List

def minimumSumSubarray(nums: List[int], l: int, r: int) -> int:
    n = len(nums)
    pre = [0] * (n + 1)
    for i, v in enumerate(nums):
        pre[i + 1] = pre[i] + v
    best = -1
    for length in range(l, r + 1):
        for i in range(n - length + 1):
            s = pre[i + length] - pre[i]
            if s > 0 and (best == -1 or s < best):
                best = s
    return best

JavaScript

var minimumSumSubarray = function(nums, l, r) {
    var n = nums.length;
    var pre = [0];
    for (var i = 0; i < n; i++) pre.push(pre[i] + nums[i]);
    var best = -1;
    for (var len = l; len <= r; len++) {
        for (var i = 0; i + len <= n; i++) {
            var s = pre[i + len] - pre[i];
            if (s > 0 && (best === -1 || s < best)) best = s;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Available Captures for Rook Easy
• Delete Columns to Make Sorted Easy
• Maximize Sum Of Array After K Negations Easy
• Nearest Smaller Element Easy
• Find X-Sum of All K-Long Subarrays I Easy
• Valid Boomerang Easy