LC209.md

Problem: Minimum Size Subarray Sum

Difficulty: Medium

Description:

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Examples:

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.

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

Constraints:

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

Solutions:

The naive approach is always to produce all of the subarrays and find the one that meets the objective. This approach has a time complexity of O(N^3) and space complexity of O(1) where N is the size of array.

def minSubArrayLen(nums, target):
    """
    :type s: int
    :type nums: List[int]
    :rtype: int
    :Time Complexity: O(N^3)
    :Space Complexity: O(N)
    """
    minLen = len(nums) + 1

    for i in range(len(nums)):
        for j in range(i, len(nums)):
            sub = nums[i : j + 1]
            if sum(sub) >= target:
                minLen = min(minLen, len(sub))

    return 0 if minLen == len(nums) + 1 else minLen

For the optimal solution, we can first use the Pre-fix Sum algorithm. This approach has a time complexity of O(N) and space complexity of O(N) where N is the size of array.

def minSubArrayLen(nums, target):
    """
    :type s: int
    :type nums: List[int]
    :rtype: int
    :Time Complexity: O(N)
    :Space Complexity: O(N)
    """
    current_sum = 0
    seen = {0: -1}
    minLen = len(nums) + 1

    for i in range(len(nums)):
        current_sum += nums[i]

        if current_sum not in seen:
            seen[current_sum] = i

        remainder = current_sum - target

        if remainder in seen:
            minLen = min(minLen, i - seen[remainder])

    return 0 if minLen == len(nums) + 1 else minLen

Based on the constraints, all numbers in nums are positive. Therefore, we can also solve this problem using Two-Pointers (Sliding-Window) algorithm.

def minSubArrayLen(nums, target):
    """
    :type s: int
    :type nums: List[int]
    :rtype: int
    :Time Complexity: O(N)
    :Space Complexity: O(1)
    """
    left = 0
    right = 0
    minLen = len(nums) + 1
    current_sum = 0

    while left < len(nums) and right < len(nums):
        current_sum += nums[right]

        if current_sum == target:
            minLen = min(minLen, right - left + 1)
            right += 1
        elif current_sum > target:
            current_sum -= nums[left]
            left += 1
        else:
            right += 1

    return 0 if minLen == len(nums) + 1 else minLen