Minimum Positive Sum Subarray solution and explanation
7 more videos on this problem
Minimum Positive Sum Subarray | Leetcode 3364Code Crafters · 1:47 · 1K views
3364. Minimum Positive Sum Subarray (Leetcode Easy)Programming Live with Larry · 6:36 · 1K views
LeetCode 3364. Minimum Positive Sum SubarrayThe CS Junction · 8:14 · 868 views
LeetCode 3364 | Minimum Positive Sum Subarray [easy]LeetCoders United · 20:46 · 316 views
Weekly Contest 425 | First 3 Problems - 3364, 3365 & 3366 | LeetcodeAmit Choraria · 28:40 · 292 views
Leetcode: Python3: 3364 Minimum Positive Sum SubarrayLuc Taylor · 5:42 · 205 views
LeetCode, 3364. Minimum Positive Sum Subarray (Easy, Arrays, Python)Sergey Chalyi · 6:54 · 95 views
Leet Code 3364. Minimum Positive Sum Subarray - JavaScriptSofia Bargues · 9:20 · 90 views
The 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.
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
Approach overview
Problem 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 1: Brute Force Subarray Sum
This approach involves calculating the sum of all possible subarrays within the given length range and finding the minimum sum greater than zero.
We iterate through all possible subarray starting and ending indices, calculating the sum for each subarray. If a sum is greater than zero and less than the current minimum, it's the new minimum.
def min_positive_subarray_sum(nums, l, r):
min_sum = float('inf')
for i in range(len(nums)):
sum_ = 0
for j in range(i, len(nums)):
sum_ += nums[j]
if l <= (j - i + 1) <= r and sum_ > 0:
min_sum = min(min_sum, sum_)
return min_sum if min_sum != float('inf') else -1
print(min_positive_subarray_sum([3, -2, 1, 4], 2, 3))class Solution {
public int minPositiveSubarraySum(int[] nums, int l, int r) {
int minSum = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length && j - i + 1 <= r; j++) {
sum += nums[j];
if (j - i + 1 >= l && sum > 0 && sum < minSum) {
minSum = sum;
}
}
}
return (minSum == Integer.MAX_VALUE) ? -1 : minSum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, -2, 1, 4};
System.out.println(sol.minPositiveSubarraySum(nums, 2, 3));
}
}#include <iostream>
#include <vector>
#include <climits>
int minPositiveSubarraySum(const std::vector<int>& nums, int l, int r) {
int minSum = INT_MAX;
int sum;
for (int i = 0; i < nums.size(); ++i) {
sum = 0;
for (int j = i; j < nums.size() && j - i + 1 <= r; ++j) {
sum += nums[j];
if (j - i + 1 >= l && sum > 0 && sum < minSum) {
minSum = sum;
}
}
}
return (minSum == INT_MAX) ? -1 : minSum;
}
int main() {
std::vector<int> nums = {3, -2, 1, 4};
int l = 2, r = 3;
std::cout << minPositiveSubarraySum(nums, l, r) << std::endl;
return 0;
}function minPositiveSubarraySum(nums, l, r) {
let minSum = Infinity;
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = i; j < nums.length && j - i + 1 <= r; j++) {
sum += nums[j];
if (j - i + 1 >= l && sum > 0 && sum < minSum) {
minSum = sum;
}
}
}
return minSum === Infinity ? -1 : minSum;
}
console.log(minPositiveSubarraySum([3, -2, 1, 4], 2, 3));#include <stdio.h>
#include <limits.h>
int minPositiveSubarraySum(int* nums, int numsSize, int l, int r) {
int minSum = INT_MAX;
int sum;
for (int i = 0; i < numsSize; i++) {
sum = 0;
for (int j = i; j < numsSize && j - i + 1 <= r; j++) {
sum += nums[j];
if (j - i + 1 >= l && sum > 0 && sum < minSum) {
minSum = sum;
}
}
}
return (minSum == INT_MAX) ? -1 : minSum;
}
int main() {
int nums[] = {3, -2, 1, 4};
int l = 2, r = 3;
printf("%d\n", minPositiveSubarraySum(nums, 4, l, r));
return 0;
}using System;
public class Solution {
public int MinPositiveSubarraySum(int[] nums, int l, int r) {
int minSum = int.MaxValue;
for (int i = 0; i < nums.Length; i++) {
int sum = 0;
for (int j = i; j < nums.Length && j - i + 1 <= r; j++) {
sum += nums[j];
if (j - i + 1 >= l && sum > 0 && sum < minSum) {
minSum = sum;
}
}
}
return (minSum == int.MaxValue) ? -1 : minSum;
}
public static void Main() {
int[] nums = {3, -2, 1, 4};
Solution sol = new Solution();
Console.WriteLine(sol.MinPositiveSubarraySum(nums, 2, 3));
}
}This Python function calculates the sum of each possible subarray within the given length range and updates the minimum sum if it's the best found so far.
Time Complexity: O(n^2) where n is the length of the array.
Space Complexity: O(1)
Approach 2: Sliding Window Approach
A sliding window approach allows us to build the subarray sum incrementally, avoiding recalculating the sum by constantly adding the next element and removing the old one. This approach is optimized by restricting the window size to the given range.
For each window ending point, we compute the sum and check if expanding the window will yield a valid subarray length while keeping track of the minimum positive sum.
def min_positive_subarray_sum(nums, l, r):
min_sum = float('inf')
curr_sum, start = 0, 0
for end in range(len(nums)):
curr_sum += nums[end]
while end - start + 1 > r:
curr_sum -= nums[start]
start += 1
if end - start + 1 >= l and curr_sum > 0:
min_sum = min(min_sum, curr_sum)
return min_sum if min_sum != float('inf') else -1
print(min_positive_subarray_sum([3, -2, 1, 4], 2, 3))class Solution {
public int minPositiveSubarraySum(int[] nums, int l, int r) {
int minSum = Integer.MAX_VALUE;
int currSum = 0, start = 0;
for (int end = 0; end < nums.length; end++) {
currSum += nums[end];
while (end - start + 1 > r) {
currSum -= nums[start++];
}
if (end - start + 1 >= l && currSum > 0) {
minSum = Math.min(minSum, currSum);
}
}
return (minSum == Integer.MAX_VALUE) ? -1 : minSum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, -2, 1, 4};
System.out.println(sol.minPositiveSubarraySum(nums, 2, 3));
}
}#include <iostream>
#include <vector>
#include <climits>
int minPositiveSubarraySum(const std::vector<int>& nums, int l, int r) {
int minSum = INT_MAX, currSum = 0;
int start = 0;
for (int end = 0; end < nums.size(); ++end) {
currSum += nums[end];
while (end - start + 1 > r) {
currSum -= nums[start++];
}
if (end - start + 1 >= l && currSum > 0) {
minSum = std::min(minSum, currSum);
}
}
return (minSum == INT_MAX) ? -1 : minSum;
}
int main() {
std::vector<int> nums = {3, -2, 1, 4};
int l = 2, r = 3;
std::cout << minPositiveSubarraySum(nums, l, r) << std::endl;
return 0;
}function minPositiveSubarraySum(nums, l, r) {
let minSum = Infinity, currSum = 0, start = 0;
for (let end = 0; end < nums.length; end++) {
currSum += nums[end];
while (end - start + 1 > r) {
currSum -= nums[start];
start++;
}
if (end - start + 1 >= l && currSum > 0) {
minSum = Math.min(minSum, currSum);
}
}
return minSum === Infinity ? -1 : minSum;
}
console.log(minPositiveSubarraySum([3, -2, 1, 4], 2, 3));#include <stdio.h>
#include <limits.h>
int minPositiveSubarraySum(int* nums, int numsSize, int l, int r) {
int minSum = INT_MAX;
int currSum = 0;
for (int i = 0, start = 0; i < numsSize; i++) {
currSum += nums[i];
if (i - start + 1 >= l) {
if (currSum > 0 && currSum < minSum) {
minSum = currSum;
}
currSum -= nums[start++];
}
// Reduce window size if it's larger than r
if (i - start + 1 > r) {
currSum -= nums[start++];
}
}
return (minSum == INT_MAX) ? -1 : minSum;
}
int main() {
int nums[] = {3, -2, 1, 4};
int l = 2, r = 3;
printf("%d\n", minPositiveSubarraySum(nums, 4, l, r));
return 0;
}using System;
public class Solution {
public int MinPositiveSubarraySum(int[] nums, int l, int r) {
int minSum = int.MaxValue, currSum = 0, start = 0;
for (int end = 0; end < nums.Length; end++) {
currSum += nums[end];
while (end - start + 1 > r) {
currSum -= nums[start];
start++;
}
if (end - start + 1 >= l && currSum > 0) {
minSum = Math.Min(minSum, currSum);
}
}
return (minSum == int.MaxValue) ? -1 : minSum;
}
public static void Main() {
int[] nums = {3, -2, 1, 4};
Solution sol = new Solution();
Console.WriteLine(sol.MinPositiveSubarraySum(nums, 2, 3));
}
}The Python code uses a sliding window technique to calculate the sum of valid subarrays and updates the minimum positive sum throughout the iteration.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1)
Approach 3: 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 nums. The space complexity is O(1).
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Subarray Sum | Time Complexity: O(n^2) where n is the length of the array. |
| Sliding Window Approach | Time Complexity: O(n) where n is the length of the array. |
| Enumeration | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Positive Sum Subarray easy or hard?
Minimum Positive Sum Subarray is categorized as an Easy problem. The main challenge is correctly iterating through subarrays within the allowed length range and keeping track of the smallest positive sum.
Minimum Positive Sum Subarray Python/Java solution
Python, Java, C++, and JavaScript implementations typically follow the same idea: iterate over valid window sizes and maintain the current sum while sliding the window. Each step updates the minimum positive sum if the current window sum is greater than zero.
How to solve Minimum Positive Sum Subarray in O(n)?
Pure O(n) is difficult when the subarray length must be between l and r because multiple window sizes must be evaluated. The practical optimization is to use a sliding window for each valid length, giving O(n * (r-l+1)) time. Prefix sums can also help compute subarray sums quickly.
Is Minimum Positive Sum Subarray asked at Google/Amazon/Meta?
Problems based on subarray sums, sliding window techniques, and prefix sums appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of constrained subarray problems are especially common in coding rounds.
What is the best approach for Minimum Positive Sum Subarray ?
The sliding window approach is typically the best practical solution. Iterate through every window size between l and r and maintain the window sum while sliding across the array. This avoids recomputing sums for each subarray and runs in O(n * (r-l+1)) time with O(1) extra space.
What data structure is used in Minimum Positive Sum Subarray ?
The solution mainly uses arrays and running sums. Sliding window techniques maintain a dynamic sum while moving across the array, and prefix sums can be used to compute subarray sums efficiently.
What is the time complexity of Minimum Positive Sum Subarray ?
The brute force solution runs in O(n²) time because it checks many possible subarrays. The optimized sliding window method processes each window in constant time and runs in O(n * (r-l+1)). Both approaches use O(1) additional space.