Minimum Size Subarray Sum

Problem Description

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.

Examples

Constraints

• 1 <= target <= 10⁹
• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁴

Monotonic Expansion and Shrinking

Since all elements in the array are positive, the prefix sum is strictly increasing. This allows us to use a sliding window. We expand the window by moving a right pointer and adding nums[right] to our cumulative sum. While the sum is greater than or equal to the target, we record the window size right - left + 1, and then attempt to shrink the window from the left by subtracting nums[left] and incrementing left to find a smaller valid subarray.

Solution 1: Dynamic Sliding Window

Expand the window to find a valid sum, then contract it to find the minimum length.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left];
                left++; // contract window
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        min_length = float('inf')
        curr_sum = 0
        left = 0
        
        for right in range(n):
            curr_sum += nums[right]
            while curr_sum >= target:
                min_length = min(min_length, right - left + 1)
                curr_sum -= nums[left]
                left += 1  # contract window
                
        return 0 if min_length == float('inf') else min_length

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int minSubArrayLen(int target, std::vector<int>& nums) {
        int n = nums.size();
        int minLength = INT_MAX;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                minLength = std::min(minLength, right - left + 1);
                sum -= nums[left];
                left++; // contract window
            }
        }
        return minLength == INT_MAX ? 0 : minLength;
    }
};

Complexity Analysis

• Time Complexity: O(n) since both pointers only move forward. Each element is visited at most twice.
• Space Complexity: O(1) auxiliary space as we only use index pointers and a sum accumulator.

Where It Breaks

If the input array contains negative numbers, the prefix sum is no longer monotonic. Contracting the window from the left could increase the sum or make it valid later, breaking the sliding window assumption. Under those conditions, a hash map of prefix sums is required.

Common Mistakes

• Incorrect return value: Returning 0 as the default value when initialized to Integer.MAX_VALUE instead of checking if any valid subarray was found.
• Off-by-one errors: Accessing indices out of bounds when contracting the left boundary of the window.

Frequently Asked Questions

Why does this run in O(n) time if there is a nested while loop? The left pointer can only increment up to n times across the entire run. This bounds the total iterations of the inner while loop to n, resulting in an amortized O(n) runtime.

Can this be solved in O(n log n) time? Yes. You can compute the prefix sum array and perform a binary search for the target sum at each index. However, this is less optimal than the O(n) sliding window approach.

← All Problems