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 3Out 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] <= 1000In #3364 Minimum Positive Sum Subarray, the goal is to identify the smallest positive sum among all possible contiguous subarrays. The key observation is that every subarray sum can be computed efficiently using incremental addition or a prefix sum technique.
A straightforward approach is to iterate over every possible starting index and expand the subarray while maintaining a running sum. Whenever the sum becomes > 0, update the minimum positive value seen so far. Using prefix sums (prefix[j] - prefix[i]) can make these calculations cleaner and avoids recomputing sums repeatedly.
Since the problem difficulty is Easy, a nested loop approach is acceptable and easy to reason about. Track the minimum positive sum during traversal and return it at the end (or an indicator like -1 if no positive subarray exists).
This method ensures all candidate subarrays are evaluated while keeping the implementation simple.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force / Nested Subarray Traversal | O(n^2) | O(1) |
| Prefix Sum Assisted Traversal | O(n^2) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Check every subarray, since constraints are small.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, prefix sums allow you to compute any subarray sum using the formula prefix[j] - prefix[i]. This avoids recalculating sums repeatedly and makes the nested traversal cleaner and easier to implement.
Problems involving subarray sums and prefix sums are common in coding interviews, including FAANG companies. While this exact problem may vary, understanding how to evaluate subarray sums efficiently is a frequently tested concept.
The problem can be solved using simple arrays and optional prefix sums. No advanced data structure is required because the constraints allow checking all subarrays efficiently for this Easy-level problem.
A common approach is to check all possible subarrays using nested loops while maintaining a running sum. Each time the sum becomes positive, update the minimum positive value. Prefix sums can simplify the implementation and reduce repeated calculations.