Sliding Window: Minimum Size Subarray Sum

Problem:

Given an array of positive integers nums and a positive integer target, find the minimum length of a contiguous subarray whose sum is greater than or equal to target. If there is no such subarray, return 0.

Example 1:

Input: nums = [2,3,1,2,4,3], target = 7
Output: 2
Explanation: The subarray [4,3] has the minimum length of 2 with a sum of 7.

Step-by-step Explanation:

To solve this problem, we can utilize the sliding window technique. Here are the steps we will follow:

1. Initialize two pointers, left and right, both pointing to the start of the array.
2. Initialize a variable minLen as infinity.
3. Initialize a variable sum as 0 to keep track of the current sum of elements in the window.
4. Loop through the array using the right pointer until it reaches the end of the array:
   1. Add the current element nums[right] to sum.
   2. While sum is greater than or equal to target, do the following:
      1. Update minLen by taking the minimum of minLen and right - left + 1.
      2. Subtract the element at the left pointer from sum and increment left by 1.
   3. Increment right by 1.
5. If minLen is still infinity, return 0 (indicating no subarray found). Otherwise, return minLen.

Here is the implementation of the above algorithm in Python:

def minSubArrayLen(nums, target):
    left = 0
    minLen = float('inf')
    sum = 0
    
    for right in range(len(nums)):
        sum += nums[right]
        
        while sum >= target:
            minLen = min(minLen, right - left + 1)
            sum -= nums[left]
            left += 1
    
    return minLen if minLen != float('inf') else 0

Complexity Analysis:

The time complexity of this algorithm is O(N), where N is the length of the input array nums. This is because both the left and right pointers will move at most N steps. Hence, the overall time complexity is linear.

The space complexity is O(1) since we are not using any additional space that grows with the input size.