< Back




209. Minimum Size Subarray Sum

Behold, a sliding window problem but this time we're minimizing the size of the sliding window. We
want the smallest window that gives us the greatest value over the array. Following the usual
paradigm, we're going to maintain a left and right pointer, and a globally available total and answer
variable.

Traversing from left to right, we add each number at the current index to the total. If the total is
equal to or exceeds the target, we compare the current window size to the current minimum window
size (which we originally set to infinity), and retain the smaller of the two. We subtract the
current value from the total and then increment the left pointer, shrinking the window.

We continue to do this until we've processed every subarray that fits our constraints. If our current
answer is still infinity, that means we failed to find a subarray greater than or equal to our
target. In this case, we return 0.

The solution is as follows:


  class Solution:
      def minSubArrayLen(self, target: int, nums: List[int]) -> int:
          n = len(nums)
          l, total, ans = 0, 0, float('inf')

          for r in range(n):
              total += nums[r]

              while (total >= target):
                  ans = min(ans, r - l + 1)
                  total -= nums[l]
                  l += 1

          return ans if ans != float('inf') else 0


_ Time Complexity:

  O(n) - We traverse the array once.

_ Space Complexity:

  O(1) - We only use a constant amount of space.