Watch 9 video solutions for Minimum Positive Sum Subarray , a easy level problem involving Array, Sliding Window, Prefix Sum. This walkthrough by Code Crafters has 1,707 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 1000Problem Overview: You are given an integer array and two integers l and r. The task is to find the smallest positive sum of any subarray whose length is between l and r (inclusive). If no such subarray exists, return -1.
Approach 1: Brute Force Subarray Sum (O(n²) time, O(1) space)
The most direct solution is to enumerate every possible subarray and compute its sum. For each starting index, expand the subarray one element at a time and keep a running sum. Whenever the current length falls within the range [l, r], check if the sum is positive and update the minimum if needed. This approach relies on basic array iteration and works because every candidate subarray is evaluated explicitly. Time complexity is O(n²) in the worst case since each start index may expand up to n elements, while space usage stays O(1).
Approach 2: Sliding Window by Length (O(n * (r-l+1)) time, O(1) space)
A more structured solution uses the sliding window technique. Instead of recomputing sums repeatedly, iterate over every valid window size from l to r. For each size, compute the first window sum, then slide the window forward by subtracting the outgoing element and adding the incoming one. This keeps each window update O(1). Every time the window moves, check whether the sum is positive and update the global minimum. Internally this behaves similarly to a fixed-length window using incremental updates rather than recomputation.
This technique avoids repeatedly summing the same elements and makes the logic cleaner. The algorithm effectively processes all subarrays whose sizes fall in the allowed range while maintaining the running sum dynamically. The total work becomes O(n * (r-l+1)), which is significantly better than recomputing sums for each candidate window.
Another way to think about the computation is through prefix sums, where the sum of any subarray can be obtained using prefix[j] - prefix[i]. Sliding windows are essentially an optimized version of this idea when window sizes are fixed.
Recommended for interviews: Start by describing the brute force enumeration because it shows you understand the search space of subarrays. Then move to the sliding window optimization that maintains a running sum for each window size. Interviewers typically expect the optimized window-based approach since it avoids repeated summation and demonstrates familiarity with common array optimization patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n²) | O(1) | Useful for understanding the problem and validating logic on small inputs. |
| Sliding Window by Length | O(n * (r-l+1)) | O(1) | Preferred approach when window sizes are bounded; avoids recomputing sums. |