[Array + Two Pointers] LC 209. Minimum Size Subarray Sum

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

Goal

• Given an array of positive integers
• minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target
• *Greedy or Sorting is not allowed!

Strategy

• Iterate through the array and add each element to the sum, one at the time
• During each iteration, we can keep subtracting the numbers (from sum) from the left until it < target

Highlight

• classic two pointers
• concept of sliding & shrinking the left window (usually a while loop)

Complexity

• Time: O(N) → as we iterate the array once
• Space: O(1) → didn’t occupy any extra space by creating additional data structures

Code

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int"""
        
        n = len(nums)
        ans = 1000000
        left = 0
        result = 0
        for i in range(n):
            result+=nums[i]
            while result >= target:
                ans = min(ans, i+1-left)
           
                result-=nums[left]
                left+=1
                
        if ans != 1000000:
            return ans
        else:
            return 0