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 <= 1001 <= 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)$.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}