Minimum Size Subarray Sum

---

Minimum Size Subarray Sum: Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

---

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

---

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

---

Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

---

Try this Problem on your own or check similar problems:

1. Minimum Operations to Reduce X to Zero
2. K Radius Subarray Averages
3. Maximum Product After K Increments

Solution:

Java

public int minSubArrayLen(int target, int[] nums) {
    int minLength = nums.length + 1, i = 0, j = 0, windowSum = 0;
    while(j < nums.length){
        windowSum += nums[j++];

        while(windowSum >= target){
            minLength = Math.min(minLength, j - i);
            windowSum -= nums[i++];
        }
    }
    return minLength % ( nums.length + 1);
}

JavaScript

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let minLength = nums.length + 1;
  let i = 0;
  let j = 0;
  let windowSum = 0;

  while (j < nums.length) {
    windowSum += nums[j++];

    while (windowSum >= target) {
      minLength = Math.min(minLength, j - i);
      windowSum -= nums[i++];
    }
  }

  return minLength % (nums.length + 1);
};

Python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        minLength = len(nums) + 1
        i = 0
        j = 0
        windowSum = 0

        while j < len(nums):
            windowSum += nums[j]
            j += 1

            while windowSum >= target:
                minLength = min(minLength, j - i)
                windowSum -= nums[i]
                i += 1

        return minLength % (len(nums) + 1)

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLength = nums.size() + 1;
        int i = 0;
        int j = 0;
        int windowSum = 0;

        while (j < nums.size()) {
            windowSum += nums[j++];

            while (windowSum >= target) {
                minLength = std::min(minLength, j - i);
                windowSum -= nums[i++];
            }
        }

        return minLength % (nums.size() + 1);
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

Implementation uses sliding window approach where we have two pointers i and j respectively pointing to the start and end of our window. When the window is valid, we can check if we are improving on one of the desired properties given by problem statement. In our problem a window is valid when the sum of all elements in the window are greater or equal to the target, and the property we're looking to optimize is the length (shorter lengths are desired by the problem statement since we're looking for the shortest subarray fulfilling the requirement). So, we move the end j of our window to the right therefore expanding the window and each time we check if the current window is fulfilling the requirement windowSum >= target (we're tracking the windowSum so we can check if window is valid). If the window is valid, we try to shorten it by moving our start i to the right thus reducing the window length and we do that until the shortening breaks the requirement (invalidates the window). We're keeping track of the shortest window fulfilling the requirement and finally we return minLength (with a trick to return 0 if there is no subarray/window with sum greater or equal to the target).