Welcome to Subscribe On Youtube

3364. Minimum Positive Sum Subarray

Description

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 <= 100
• 1 <= l <= r <= nums.length
• -1000 <= nums[i] <= 1000

Solutions

Solution 1: 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 $\textit{nums}$. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int minimumSumSubarray(List<Integer> nums, int l, int r) {
          int n = nums.size();
          final int inf = Integer.MAX_VALUE;
          int ans = inf;
          for (int i = 0; i < n; ++i) {
              int s = 0;
              for (int j = i; j < n; ++j) {
                  s += nums.get(j);
                  int k = j - i + 1;
                  if (k >= l && k <= r && s > 0) {
                      ans = Math.min(ans, s);
                  }
              }
          }
          return ans == inf ? -1 : ans;
      }
  }
  
  

• class Solution {
  public:
      int minimumSumSubarray(vector<int>& nums, int l, int r) {
          int n = nums.size();
          const int inf = INT_MAX;
          int ans = inf;
          for (int i = 0; i < n; ++i) {
              int s = 0;
              for (int j = i; j < n; ++j) {
                  s += nums[j];
                  int k = j - i + 1;
                  if (k >= l && k <= r && s > 0) {
                      ans = min(ans, s);
                  }
              }
          }
          return ans == inf ? -1 : ans;
      }
  };
  
  

• class Solution:
      def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
          n = len(nums)
          ans = inf
          for i in range(n):
              s = 0
              for j in range(i, n):
                  s += nums[j]
                  if l <= j - i + 1 <= r and s > 0:
                      ans = min(ans, s)
          return -1 if ans == inf else 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
  }
  
  

• 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;
  }
  
  

All Problems

All Solutions