0209-minimum-size-subarray-sum

Try it on leetcode

Description

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)).

Solution(Python)

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        #  target = 7, nums = [2,3,1,2,4,3]
        # minimal length of subarray int   sum(subarray) >= target
        # 
        #  valid window -> 7
        #  2 3 1 2 4 3
        #  
        #  nums = [3] k = 3 ; 1
        # nums = [1,2,3] k =100; 0
        #
        # left ..right
        # sum = 8
        # target = 7
        # sum >= target  left += 1
        #       sum -= nums[left]

        #  expand right
        #    sum +=nums[right]
        #    while sum >= k
        #        update answer
        #        remove nums[left]
        #        left ++
        # 
        # target = 7
        #   2 3 1 2 4 3
        # left =0
        # sum = 0
        # ans= float(inf)
        # right =0 sum  2
        # right = 1 sum 5
        # right = 2 ans = 2 sum 8 - 2 = 6  left = 1
        # 
        # coorect condition cur_sum >= target remove left 
        l = 0
        cur_sum = 0
        ans = float('inf')
        for r in range(len(nums)):
            cur_sum += nums[r]
            while cur_sum >= target and l < len(nums):
                ans= min(ans, r - l + 1)
                cur_sum -= nums[l]
                l+=1
                
        return ans if ans != float('inf') else 0

Dry Run