3364. Minimum Positive Sum Subarray
EasyView on LeetCode
Problem Overview
The answer is the smallest positive sum among contiguous windows whose length sits between l and r.
Intuition
The answer is the smallest positive sum among contiguous windows whose length sits between l and r. With n at most 100, every allowed length can be scanned directly. For a fixed length, a sliding window maintains the running sum in constant time per move. Only sums greater than zero compete for the answer. Because the values are integers, no positive sum can be smaller than 1, so the search can stop as soon as that value appears. If every window sum is non-positive, the method returns -1.
Algorithm
- 1Initialize the answer to a large sentinel.
- 2For every window length from l through r, build the sum of the first window of that length.
- 3If that sum is positive, keep it as a candidate minimum.
- 4Slide the window across the rest of the array, adding the entering value and removing the leaving value, and update the answer on every positive sum.
- 5Return 1 as soon as the answer becomes 1. Otherwise return the best positive sum, or -1 when none exists.
Example Walkthrough
Input: nums = [3, -2, 1, 4], l = 2, r = 3
- 1.Length 2 windows include [3, -2] with sum 1 and [1, 4] with sum 5.
- 2.Length 3 windows include [3, -2, 1] with sum 2 and [-2, 1, 4] with sum 3.
- 3.The smallest positive sum among those windows is 1.
Output: 1
Common Pitfalls
- •Zero and negative sums do not qualify. Only strictly positive sums update the answer.
- •The window length must stay inside [l, r]. A shorter or longer subarray is invalid even if its sum is smaller.
- •Return -1 when no positive window exists. Do not return 0 in that case.
- •Finding sum 1 is enough to stop. No integer array can produce a smaller positive sum.
3364.cs
C#
// Approach: For every length in [l, r], slide a fixed window across nums and
// keep the smallest window sum that is still positive. Integer sums cannot
// beat 1, so the search stops as soon as that value appears. With n at most
// 100 the quadratic scan is already the tight practical bound.
// Time: O(n · (r - l + 1)) Space: O(1)
public class Solution
{
public int MinimumSumSubarray(IList<int> nums, int l, int r)
{
int n = nums.Count;
int ans = int.MaxValue;
for (int windowSize = l; windowSize <= r; ++windowSize)
{
int sum = 0;
for (int i = 0; i < windowSize; ++i)
sum += nums[i];
if (sum > 0)
ans = Math.Min(ans, sum);
for (int i = windowSize; i < n; ++i)
{
sum += nums[i] - nums[i - windowSize];
if (sum > 0)
ans = Math.Min(ans, sum);
}
if (ans == 1)
return 1;
}
return ans == int.MaxValue ? -1 : ans;
}
}
Was this solution helpful?
Related Problems
- 862. Shortest Subarray with Sum at Least K(Hard)
- 1248. Count Number of Nice Subarrays(Medium)
- 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum(Medium)
- 1658. Minimum Operations to Reduce X to Zero(Medium)
- 2106. Maximum Fruits Harvested After at Most K Steps(Unknown)
- 2302. Count Subarrays With Score Less Than K(Hard)