Leetcode # 209. Minimum Size Subarray Sum

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

Solution: Sliding Window

Time Complexity: O(len(nums))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    ans = inf
    left = curr = 0
    for right in range(0, len(nums)):
      # do logic here to add arr[right] to curr
      curr += nums[right]
    
      while curr - nums[left] >= target:
        # remove arr[left] from curr
        curr -= nums[left]
        left += 1
        
      # update ans
      if curr >= target:
        ans = min(ans, right - left + 1) 
    
    return 0 if ans is inf else ans

Solution – Time Complexity: O(len(nums) * log(len(nums)))

• sums[i] := nums[i] + (sums[i – 1] if i > 0 else 0)
• ∀ sums[i], if ∃ j ∈ [k for k in range(i) if sums[i] – (sums[k – 1] if k > 0 else 0) >= target]
  ⇒ ans = min(ans, i – j + 1)
  (Find the j with binary search (O(log(n))) 
    then you get O(len(nums) * log(len(nums))))

Last Updated on 2023/08/16 by A1go