Leetcode Problem 209 Minimum Size Subarrary Sum.txt

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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104
 

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).




Hint: 
Use sliding window
Initialize max subarray size equal to size of the nums
Edge: If total sum is less than target then there is no subarrary that is possible
Start Iterating and calculating current sum
    This is our rightPTR
    While sum becomes greater or equal to the target
        Update the sum by removing the left element
        calculate min window size by rightptr-leftprt + 1
        move leftprt by one
Return the minWindow



class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        leftIndex = 0
        rightIndex = 0
        windowSum = 0
        minWindow = len(nums)

        if sum(nums) < target:
            return 0
        
        for i in range(len(nums)):
            windowSum += nums[i]
            rightIndex = i
            while windowSum >= target:
                windowSum -= nums[leftIndex]
                print(f"l={leftIndex} r={rightIndex} sum={windowSum}")
                minWindow = min(minWindow, (rightIndex-leftIndex)+1)
                leftIndex += 1
                print(f"minWindow={minWindow}")
        return minWindow