Minimum Size Subarray Sum [Medium] — Sliding Window

Problem Statement

Given a positive integer target and an array of positive integers, return the minimal length of a contiguous subarray with sum >= target, or 0 if no such subarray exists.

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

Intuition

Shrinkable sliding window: expand right pointer, then shrink left pointer while window sum >= target, tracking minimum window size.

Solutions

C

int minSubArrayLen(int target, int* nums, int n) {
    int left = 0, sum = 0, ans = INT_MAX;
    for (int right = 0; right < n; right++) {
        sum += nums[right];
        while (sum >= target) { ans = fmin(ans, right-left+1); sum -= nums[left++]; }
    }
    return ans == INT_MAX ? 0 : ans;
}

C++

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

Java

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, ans = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) { ans = Math.min(ans, right-left+1); sum -= nums[left++]; }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

JavaScript

var minSubArrayLen = function(target, nums) {
    let left = 0, sum = 0, ans = Infinity;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) { ans = Math.min(ans, right-left+1); sum -= nums[left++]; }
    }
    return ans === Infinity ? 0 : ans;
};

Python

def minSubArrayLen(target: int, nums: list[int]) -> int:
    left = s = 0
    ans = float('inf')
    for right, val in enumerate(nums):
        s += val
        while s >= target:
            ans = min(ans, right - left + 1)
            s -= nums[left]
            left += 1
    return 0 if ans == float('inf') else ans

Complexity

Time: O(n) — each element enters/leaves window once
Space: O(1)

Follow-up O(n log n)

Binary search on prefix sums for when the array can have negatives.