Skip to content

3364. Minimum Positive Sum Subarray 👍

  • Time: $O(n^2)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int minimumSumSubarray(vector<int>& nums, int l, int r) {
    int ans = INT_MAX;

    for (int windowSize = l; windowSize <= r; ++windowSize) {
      int sum = accumulate(nums.begin(), nums.begin() + windowSize, 0);
      if (sum > 0)
        ans = min(ans, sum);
      for (int i = windowSize; i < nums.size(); ++i) {
        sum -= nums[i - windowSize];
        sum += nums[i];
        if (sum > 0)
          ans = min(ans, sum);
      }
    }

    return ans == INT_MAX ? -1 : ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int minimumSumSubarray(List<Integer> nums, int l, int r) {
    int ans = Integer.MAX_VALUE;

    for (int windowSize = l; windowSize <= r; ++windowSize) {
      int sum = 0;
      for (int i = 0; i < windowSize; ++i)
        sum += nums.get(i);
      if (sum > 0)
        ans = Math.min(ans, sum);
      for (int i = windowSize; i < nums.size(); ++i) {
        sum -= nums.get(i - windowSize);
        sum += nums.get(i);
        if (sum > 0)
          ans = Math.min(ans, sum);
      }
    }

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def minimumSumSubarray(self, nums: list[int], l: int, r: int) -> int:
    ans = math.inf

    for windowSize in range(l, r + 1):
      windowSum = sum(nums[:windowSize])
      if windowSum > 0:
        ans = min(ans, windowSum)
      for i in range(windowSize, len(nums)):
        windowSum -= nums[i - windowSize]
        windowSum += nums[i]
        if windowSum > 0:
          ans = min(ans, windowSum)

    return -1 if ans == math.inf else ans