Data Structures & Algorithms - Sliding Window: 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

Playground: Leetcode 209

General Observations

Q. Can nums contain negative integers?
A. No, 1 <= nums[i] <= 10⁴.

Brute Force: Nested Loop Approach

Use nested loops to explore all possible subarrays, aggregating their sums, and whenever the sum reaches or exceeds the target, update the minimum length and stop expanding the subarray further.

Visualization

Algorithm

public int minSubArrayLen(int target, int[] nums) {
    int minLength = Integer.MAX_VALUE;
    for(int i = 0; i < nums.length; i++) {
        int currSum = 0;
        for(int j = i; j < nums.length; j++) {
            currSum += nums[j];
            if(currSum >= target) {
                minLength = Math.min(minLength, j-i+1);
                break;
            }
        }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

Time Complexity

Considering the operations inside the inner loop are constant time, the time complexity of the algorithm only depends on how many times the inner loop runs.

In the worst case, for each starting index i, the inner loop runs (n-i) times:

Total operations performed = n + (n-1) + (n-2) + (n-3) + ... + 1 = n(n+1)/2 = (n² + n)/2. Ignoring the constants and lower-order terms, the overall time complexity simplifies to O(n²).

Space Complexity

We are not using any extra space, hence overall space complexity = O(1).

Optimization: Sliding Window Approach

We can use two pointers: left and right to maintain a sliding window representing the current subarray.

Since all elements in the nums array are positive, the total sum behaves predictably. When we move the right pointer forward, the sum increases, and when we move the left pointer forward, the sum decreases.

This allows us to treat a portion of the array as a dynamic window that we can expand to reach the target sum and then shrink to find the smallest possible valid subarray. Instead of recomputing sums for every possible subarray, we reuse previous computations by adjusting the window, making the process much more efficient.

Visualization

Algorithm

public int minSubArrayLen(int target, int[] nums) {
    int minLength = Integer.MAX_VALUE;
    int currSum = 0;
    int left = 0;

    for (int right = 0; right < nums.length; right++) {
        currSum += nums[right];

        while(currSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            currSum -= nums[left];
            left++;
        }
    }

    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

Time Complexity

In the worst case, each element would be:

• Added to the currSum once (when right pointer moves forward)
• Removed from the currSum once (when left pointer moves forward)

Hence, overall time complexity = O(2n) ~ O(n).

Space Complexity

We are not using any extra space. Hence, overall space complexity = O(1).