Minimum Size Subarray Sum

How it works

We can precompute prefix sums so that the sum of any subarray from index i to j is prefixSum[j+1] - prefixSum[i]. Since all numbers are positive, the prefix sum array is strictly increasing. For each starting index i, we can binary search for the smallest ending index j where the subarray sum is at least target.

Steps

1. Build a prefix sum array where prefixSum[i] represents the sum of the first i elements.
2. For each starting index i:
   • Binary search in range [i, n] to find the smallest j where prefixSum[j+1] - prefixSum[i] >= target.
   • If found, update res with j - i + 1.
3. Return res % (n + 1) to handle the case where no valid subarray exists (returns 0).

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Using Strict Equality Instead of Greater-Than-or-Equal

The problem asks for sum greater than or equal to target, not exactly equal. A common bug is checking if (sum == target) instead of if (sum >= target). This causes the algorithm to miss valid subarrays where the sum exceeds the target, often returning 0 when a valid answer exists.

Not Handling the No-Solution Case

When no subarray sums to at least target, you must return 0. Initializing res to n + 1 or infinity and forgetting to check this at the end leads to returning invalid values. Always verify whether res was ever updated before returning it.

Shrinking the Window Too Aggressively

In the sliding window approach, some implementations shrink the window by moving the left pointer multiple times in a single iteration without rechecking the sum condition. The correct approach uses a while loop that continues shrinking only as long as sum >= target, updating the minimum length at each valid position.

from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        prefixSum = [0] * (n + 1)
        for i in range(n):
            prefixSum[i + 1] = prefixSum[i] + nums[i]

        res = n + 1
        for i in range(n):
            l, r = i, n
            while l < r:
                mid = (l + r) // 2
                curSum = prefixSum[mid + 1] - prefixSum[i]
                if curSum >= target:
                    r = mid
                else:
                    l = mid + 1
            if l != n:
                res = min(res, l - i + 1)

        return res % (n + 1)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<int> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int res = n + 1;
        for (int i = 0; i < n; i++) {
            int l = i, r = n;
            while (l < r) {
                int mid = (l + r) / 2;
                int curSum = prefixSum[mid + 1] - prefixSum[i];
                if (curSum >= target) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l != n) {
                res = min(res, l - i + 1);
            }
        }

        return res % (n + 1);
    }
};