Leetcode 209. Minimum Size Subarray Sum

Problem

Leetcode 209 - Minimum Size Subarray Sum

Example:

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.

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Approach

We can use sliding window technique to get the total, and while total is bigger or equal to target, then we update the length, then decrement nums[left], and increment left index.

We increment right once the while loop is done to get a new total.

Visualization of the Approach:

nums = [2,3,1,2,4,3]
        lr
total = 2

nums = [2,3,1,2,4,3]
        l r
total = 5

nums = [2,3,1,2,4,3]
        l   r
total = 6

nums = [2,3,1,2,4,3]
        l     r
total = 8
Since total >= target, update minLen = 4, increment l and target -= nums[left]

nums = [2,3,1,2,4,3]
          l   r
total = 6

nums = [2,3,1,2,4,3]
          l     r
total = 10
Since total >= target, update minLen = 4, increment l and target -= nums[left]

nums = [2,3,1,2,4,3]
            l   r
total = 7
Since total >= target, update minLen = 3, increment l and target -= nums[left]

nums = [2,3,1,2,4,3]
              l r
total = 6

nums = [2,3,1,2,4,3]
              l   r
total = 9
Since total >= target, update minLen = 3, increment l and target -= nums[left]

nums = [2,3,1,2,4,3]
                l r
total = 7
Since total >= target, update minLen = 2, increment l and target -= nums[left]

nums = [2,3,1,2,4,3]
                  lr
total = 3

minLen = 2

Here is the Python code for the solution:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        total = 0
        left, right = 0, 0
        minLen = float('inf')

        while right < len(nums):
            total += nums[right]
            
            while target <= total:
                minLen = min(minLen, right-left+1)
                total -= nums[left]
                left += 1
        
        right += 1
    
    return minLen if minLen > 0 and minLen != float('inf') else 0

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$