Minimum Size Subarray Sum

Problem Link

Minimum Size Subarray Sum – LeetCode #209

Problem Statement

You are given an array of positive integers nums and a positive integer target.

Return the minimum length of a contiguous subarray of which the sum is greater than or equal to target.
If there is no such subarray, return 0.

Examples

• Input: target = 7, nums = [2,3,1,2,4,3]
  Output: 2
  Explanation: Subarray [4,3] has the minimum length with sum ≥ 7.

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

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

Constraints

• 1 <= target <= 10⁹

• 1 <= nums.length <= 10⁵

• 1 <= nums[i] <= 10⁴

Intuition

We want to find the smallest window (subarray) whose elements sum to at least target.

This problem naturally fits the Variable Size Sliding Window – Conditional Based pattern:

• Expand the window by moving the right pointer.

• Shrink the window from the left while the current window sum satisfies the condition (sum ≥ target).

• Keep track of the minimum length during the process.

Approach

1. Initialize two pointers l = 0, r = 0.

2. Maintain a running sum and set minLen to Integer.MAX_VALUE.

3. Loop through the array with r:

   • Add nums[r] to sum.

   • If sum ≥ target, try shrinking the window from the left while keeping the sum valid:

     • Update minLen with the current window length r - l + 1.

     • Subtract nums[l] and increment l.

4. After the loop, return minLen if updated, otherwise return 0.

Java Code

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;

        for (int r = 0; r < nums.length; r++) {
            sum += nums[r];

            while (sum >= target) {
                min = Math.min(min, r - l + 1);
                sum -= nums[l];
                l++;
            }
        }

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

Time and Space Complexity

• Time Complexity: O(n)
  Both pointers l and r each traverse the array at most once. The inner while loop runs only when the condition sum ≥ target is met.

• Space Complexity: O(1)
  Constant extra space is used regardless of input size.

Dry Run

Input:

target = 7, nums = [2, 3, 1, 2, 4, 3]

Steps:

• r = 0, sum = 2

• r = 1, sum = 5

• r = 2, sum = 6

• r = 3, sum = 8 → valid window → update min = 4

  • Shrink → sum = 6, l = 1

• r = 4, sum = 10 → valid → min = 4

  • Shrink → sum = 7, l = 2 → min = 3

  • Shrink → sum = 6, l = 3

• r = 5, sum = 9 → valid → min = 3

  • Shrink → sum = 7, l = 4 → min = 2

  • Shrink → sum = 3, l = 5

Final min = 2

Conclusion

This problem demonstrates the power of the Variable Size Sliding Window – Condition Based pattern, especially when the task is to minimize or maximize a window size based on a condition (in this case, a sum threshold).

The key to solving it efficiently is:

• Expanding the window greedily

• Shrinking it as much as possible while maintaining the constraint

This technique is highly reusable for:

• Minimum/maximum length subarrays with sum or frequency conditions

• Optimization problems involving streaming or large datasets