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

Approach 1: Two pointers (sliding window).

Approach 2: Binary search.

Code (Python)

Approach 1:

    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # O(N): sliding window
        min_len = float('inf')
        total = 0
        left = 0
        for right in range(len(nums)):
            total += nums[right]
            if total < s:
                continue
            while left + 1 <= right and total - nums[left] >= s:
                total -= nums[left]
                left += 1
            min_len = min(min_len, right - left + 1)
        
        return min_len if min_len < float('inf') else 0

Approach 2:

    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # O(NlogN): binary search
        if sum(nums) < s:
            return 0
        
        lo, hi = 1, len(nums)
        # find first(lowest) item such that has_sum_>=_s(item) == True
        while lo < hi:
            mid = (lo + hi) // 2
            if self._has_sum(mid, nums, s):
                hi = mid
            else:
                lo = mid + 1
        return lo
    
    def _has_sum(self, length, nums, target):
        total = sum(nums[:length])
        if total >= target:
            return True
        for i in range(length, len(nums)):
            total += nums[i]
            total -= nums[i-length]
            if total >= target:
                return True
        return False

Code (C++)

Approach 1:

// Two pointers.
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int head = 0;
        int tail = 0;
        int sum = 0;
        int max = 0;
        int minLen = 0;
        while (sum >= s || tail < nums.size())
        {
            if (sum < s)
            {
                sum += nums[tail];
                tail++;
            }
            else
            {
                if (minLen == 0 || minLen > tail - head)
                    minLen = tail - head;
                sum -= nums[head];
                head++;
            }
        }
        return minLen;
    }
};

Approach 2:

// Binary search.
class Solution {
private:
    int binarySearch(int target, int sum[], int head, int tail) {
        while (head <= tail)
        {
            int mid = head + (tail - head) / 2;
            if (sum[mid] < target)
                head = mid + 1;
            else if (sum[mid] > target)
                tail = mid - 1;
            else
                return mid;
        }
        return head;
    }
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0 || s == 0)
            return 0;
        int sum[n];
        sum[0] = nums[0];
        for (int i = 1; i < n; ++i)
        {
            sum[i] = sum[i-1] + nums[i];
        }
        int minLen = 0;
        for (int head = 0; head < n; ++head)
        {
            int tail = binarySearch(s + sum[head] - nums[head], sum, head, n - 1);
            if (tail >= n)
                break;
            if (minLen == 0 || minLen > tail - head + 1)
                minLen = tail - head + 1;
        }
        return minLen;
    }
};