Skip to content

3364. Minimum Positive Sum Subarray

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.

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

 

Example 1:

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:

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:

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

Solutions

Solution 1: Enumeration

We can enumerate the left endpoint $i$ of the subarray, then enumerate the right endpoint $j$ from $i$ to $n$ within the interval $[i, n)$. We calculate the sum $s$ of the interval $[i, j]$. If $s$ is greater than $0$ and the interval length is between $[l, r]$, we update the answer.

Finally, if the answer is still the initial value, it means no subarray meets the conditions, so we return $-1$. Otherwise, we return the answer.

The time complexity is $O(n^2)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $O(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)
        ans = inf
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                if l <= j - i + 1 <= r and s > 0:
                    ans = min(ans, s)
        return -1 if ans == inf else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minimumSumSubarray(List<Integer> nums, int l, int r) {
        int n = nums.size();
        final int inf = Integer.MAX_VALUE;
        int ans = inf;
        for (int i = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += nums.get(j);
                int k = j - i + 1;
                if (k >= l && k <= r && s > 0) {
                    ans = Math.min(ans, s);
                }
            }
        }
        return ans == inf ? -1 : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        const int inf = INT_MAX;
        int ans = inf;
        for (int i = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += nums[j];
                int k = j - i + 1;
                if (k >= l && k <= r && s > 0) {
                    ans = min(ans, s);
                }
            }
        }
        return ans == inf ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minimumSumSubarray(nums []int, l int, r int) int {
    const inf int = 1 << 30
    ans := inf
    for i := range nums {
        s := 0
        for j := i; j < len(nums); j++ {
            s += nums[j]
            k := j - i + 1
            if k >= l && k <= r && s > 0 {
                ans = min(ans, s)
            }
        }
    }
    if ans == inf {
        return -1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function minimumSumSubarray(nums: number[], l: number, r: number): number {
    const n = nums.length;
    let ans = Infinity;
    for (let i = 0; i < n; ++i) {
        let s = 0;
        for (let j = i; j < n; ++j) {
            s += nums[j];
            const k = j - i + 1;
            if (k >= l && k <= r && s > 0) {
                ans = Math.min(ans, s);
            }
        }
    }
    return ans == Infinity ? -1 : ans;
}

Comments