209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

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.

Example 2:

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

Example 3:

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

🔍 Thought Process:

1. Brute Force (Inefficient):
   Check every possible subarray and compute the sum. Time complexity: O(n²) → too slow for large input.
2. Sliding Window (Optimal):
   Since all elements are positive, we can use a sliding window approach:
   • Expand the window by moving the right pointer (end).
   • Once the sum inside the window ≥ target, move the left pointer (start) to try to shrink the window and still satisfy the condition.
   • Track the minimum window length that meets the condition.

✅ Time Complexity: O(n)

Each element is visited at most twice (once by end, once by start), so it’s linear.

🔧 Implementations

🔷 Go

func minSubArrayLen(target int, nums []int) int {
    start, sum, minLen := 0, 0, len(nums)+1
    for end := 0; end < len(nums); end++ {
        sum += nums[end]
        for sum >= target {
            if end-start+1 < minLen {
                minLen = end - start + 1
            }
            sum -= nums[start]
            start++
        }
    }
    if minLen == len(nums)+1 {
        return 0
    }
    return minLen
}

🔸 PHP

function minSubArrayLen($target, $nums) {
    $start = 0;
    $sum = 0;
    $minLen = count($nums) + 1;

    for ($end = 0; $end < count($nums); $end++) {
        $sum += $nums[$end];
        while ($sum >= $target) {
            $minLen = min($minLen, $end - $start + 1);
            $sum -= $nums[$start];
            $start++;
        }
    }

    return $minLen === count($nums) + 1 ? 0 : $minLen;
}

🔹 C#

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int start = 0, sum = 0;
        int minLen = nums.Length + 1;

        for (int end = 0; end < nums.Length; end++) {
            sum += nums[end];
            while (sum >= target) {
                minLen = Math.Min(minLen, end - start + 1);
                sum -= nums[start];
                start++;
            }
        }

        return minLen == nums.Length + 1 ? 0 : minLen;
    }
}