---
tags: data_structure_python
---

# Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

**Example:**

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

**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

## Solution 1: Naive

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # Time complexity: O(n^2)
        mini, n = float(inf), len(nums)
        for i in range(n):
            sum = 0
            for j in range(i, n):
                sum += nums[j]
                if sum >= s:
                    mini = min(mini, j-i+1)
                    break
        return mini if mini != float(inf) else 0

## Solution 2: Sliding Window

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # Time complexity: O(n)
        mini, n = float(inf), len(nums)
        sum, beg = 0, 0
        for i in range(n):
            sum += nums[i] 
            while sum >= s:
                mini = min(mini, i-beg+1)
                sum += -nums[beg]
                beg += 1    
        return mini if mini != float(inf) else 0