Minimum Size Subarray Sum

Problem

Given an array of positive integers and a target, find the minimal length of a contiguous subarray whose sum is at least the target. Return 0 if no such subarray exists.

Input:  target = 7, nums = [2,3,1,2,4,3]
Output: 2   (subarray [4,3])

Python Solution

def min_subarray_len(target, nums):
    left = 0
    window_sum = 0
    best = len(nums) + 1
    for right, num in enumerate(nums):
        window_sum += num
        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return best if best <= len(nums) else 0

C++ Solution

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, windowSum = 0, best = nums.size() + 1;
    for (int right = 0; right < nums.size(); right++) {
        windowSum += nums[right];
        while (windowSum >= target) {
            best = min(best, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
    return best <= (int)nums.size() ? best : 0;
}

Java Solution

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, windowSum = 0, best = nums.length + 1;
        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right];
            while (windowSum >= target) {
                best = Math.min(best, right - left + 1);
                windowSum -= nums[left];
                left++;
            }
        }
        return best <= nums.length ? best : 0;
    }
}

Complexity

Time: O(n) — the left pointer only ever moves forward, so total work stays linear. Space: O(1) — only the running sum and two pointers are used.