DDSA Solutions

3364. Minimum Positive Sum Subarray

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

  1. 1Initialize the answer to a large sentinel.
  2. 2For every window length from l through r, build the sum of the first window of that length.
  3. 3If that sum is positive, keep it as a candidate minimum.
  4. 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.
  5. 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. 1.Length 2 windows include [3, -2] with sum 1 and [1, 4] with sum 5.
  2. 2.Length 3 windows include [3, -2, 1] with sum 2 and [-2, 1, 4] with sum 3.
  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