Problem

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.

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


Input: nums = [3, -2, 1, 4], l = 2, r = 3

Output: 1

Explanation:

The subarrays of length between `l = 2` and `r = 3` where the sum is greater
than 0 are:

  * `[3, -2]` with a sum of 1
  * `[1, 4]` with a sum of 5
  * `[3, -2, 1]` with a sum of 2
  * `[-2, 1, 4]` with a sum of 3

Out of these, the subarray `[3, -2]` has a sum of 1, which is the smallest
positive sum. Hence, the answer is 1.

Example 2

1
2
3
4
5
6
7
8
9


Input: nums = [-2, 2, -3, 1], l = 2, r = 3

Output: -1

Explanation:

There is no subarray of length between `l` and `r` that has a sum greater than
0. So, the answer is -1.

Example 3

1
2
3
4
5
6
7
8
9


Input: nums = [1, 2, 3, 4], l = 2, r = 4

Output: 3

Explanation:

The subarray `[1, 2]` has a length of 2 and the minimum sum greater than 0.
So, the answer is 3.

Constraints

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

Solution

Method 1 – Brute Force Sliding Window

Intuition

Try all subarrays of length between l and r, compute their sums, and track the minimum positive sum.

Approach

  1. For each possible window size from l to r:
  2. Slide the window over the array, compute the sum.
  3. If sum > 0, update the minimum.
  4. Return the minimum found, or -1 if none.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
#include <climits>
class Solution {
public:
    int minimumSubarraySum(std::vector<int>& nums, int l, int r) {
        int n = nums.size(), ans = INT_MAX;
        for (int len = l; len <= r; ++len) {
            int sum = 0;
            for (int i = 0; i < len; ++i) sum += nums[i];
            if (sum > 0) ans = std::min(ans, sum);
            for (int i = len; i < n; ++i) {
                sum += nums[i] - nums[i-len];
                if (sum > 0) ans = std::min(ans, sum);
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func minimumSubarraySum(nums []int, l, r int) int {
    n, ans := len(nums), 1<<31-1
    for length := l; length <= r; length++ {
        sum := 0
        for i := 0; i < length; i++ { sum += nums[i] }
        if sum > 0 && sum < ans { ans = sum }
        for i := length; i < n; i++ {
            sum += nums[i] - nums[i-length]
            if sum > 0 && sum < ans { ans = sum }
        }
    }
    if ans == 1<<31-1 { return -1 }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int minimumSubarraySum(int[] nums, int l, int r) {
        int n = nums.length, ans = Integer.MAX_VALUE;
        for (int len = l; len <= r; ++len) {
            int sum = 0;
            for (int i = 0; i < len; ++i) sum += nums[i];
            if (sum > 0) ans = Math.min(ans, sum);
            for (int i = len; i < n; ++i) {
                sum += nums[i] - nums[i-len];
                if (sum > 0) ans = Math.min(ans, sum);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun minimumSubarraySum(nums: IntArray, l: Int, r: Int): Int {
        var ans = Int.MAX_VALUE
        for (len in l..r) {
            var sum = nums.take(len).sum()
            if (sum > 0) ans = minOf(ans, sum)
            for (i in len until nums.size) {
                sum += nums[i] - nums[i-len]
                if (sum > 0) ans = minOf(ans, sum)
            }
        }
        return if (ans == Int.MAX_VALUE) -1 else ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minimumSubarraySum(self, nums: list[int], l: int, r: int) -> int:
        n, ans = len(nums), float('inf')
        for length in range(l, r+1):
            s = sum(nums[:length])
            if s > 0: ans = min(ans, s)
            for i in range(length, n):
                s += nums[i] - nums[i-length]
                if s > 0: ans = min(ans, s)
        return -1 if ans == float('inf') else ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn minimum_subarray_sum(nums: Vec<i32>, l: i32, r: i32) -> i32 {
        let n = nums.len();
        let mut ans = i32::MAX;
        for len in l..=r {
            let mut sum: i32 = nums.iter().take(len as usize).sum();
            if sum > 0 { ans = ans.min(sum); }
            for i in len as usize..n {
                sum += nums[i] - nums[i-len as usize];
                if sum > 0 { ans = ans.min(sum); }
            }
        }
        if ans == i32::MAX { -1 } else { ans }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minimumSubarraySum(nums: number[], l: number, r: number): number {
        let n = nums.length, ans = Infinity;
        for (let len = l; len <= r; ++len) {
            let sum = nums.slice(0, len).reduce((a,b)=>a+b,0);
            if (sum > 0) ans = Math.min(ans, sum);
            for (let i = len; i < n; ++i) {
                sum += nums[i] - nums[i-len];
                if (sum > 0) ans = Math.min(ans, sum);
            }
        }
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — Try all window sizes and slide.
  • 🧺 Space complexity: O(1) — Only variables.