209.Minimum_Size_Subarray_Sum(Medium).md

209. Minimum Size Subarray Sum (Medium)

Date and Time: Jul 10, 2024, 16:24 (EST)

Link: https://leetcode.com/problems/minimum-size-subarray-sum/

Question:

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

Edge Case:

Input: target = 4, nums = [4]

Output: 1

Constraints:

• 1 <= target <= 10^9

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^4

KeyPoints:

Maintain a sliding window with curSum, we repeatly add curSum += num until curSum >= target. We update res = min(res, r - l + 1) and shrink the sliding window by removing the left-most element, trying to find the minimal length.

My Solution:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # Maintain a sliding winow with curSum
        # If curSum < target, expanding the window from the right most
        # If curSum >= target, update res = min(res, r - l + 1)
        # Then, shrink the window by removing the left most elem
        
        # TC: O(n), n = len(nums), SC: O(1)
        l, curSum = 0, 0
        res = float("inf")    # minimal length to return
        for r in range(len(nums)):
            curSum += nums[r]
            while curSum >= target:
                res = min(res, r - l + 1)
                # Shrink window by removing the left-most element
                curSum -= nums[l]
                l += 1
        # when we can't find subarray, return 0 instead
        return res if res != float("inf") else 0

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