Minimum Size Subarray Sum (Sliding Window Technique)

Problem Understanding

You are given:

• An array of positive integers nums.

• A positive integer target.

Your task is to find the minimum length of a contiguous subarray such that the sum is greater than or equal to target.
If no such subarray exists, return 0.

Example

Input:
target = 7, nums = [2,3,1,2,4,3]
Output:
2 → because the subarray [4,3] has a sum of 7.

Brute Force Idea (Not Used)

You can try all subarrays, calculate their sums, and check if the sum is greater than or equal to the target.
However, this takes O(n²) time, which is inefficient for large arrays.

Efficient Approach – Sliding Window (Two Pointers)

Since all elements in the array are positive, we can use the sliding window technique:

• Use two pointers: left and right to represent the current window.

• Move the right pointer to expand the window and increase the sum.

• Once the window’s sum is greater than or equal to target, try moving the left pointer to shrink the window and find the shortest valid length.

• Repeat the process until the end of the array.

Step-by-Step Explanation

1. Initialize:

   • left = 0: start of the window

   • current_sum = 0: the sum of the current window

   • min_length = INT_MAX: to track the smallest valid subarray length

2. Move the right pointer across the array:

   • Add nums[right] to current_sum

3. While current_sum >= target:

   • Update min_length with the size of the current window

   • Subtract nums[left] from current_sum and move left forward to try a smaller window

4. After the loop:

   • If min_length is still INT_MAX, return 0 (no valid subarray found)

   • Otherwise, return min_length

Time and Space Complexity

• Time Complexity: O(n)
  Each element is visited at most twice (once by right, once by left).

• Space Complexity: O(1)
  Only a few variables are used. No extra space required.

Test Case Walkthrough

Input:

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

Goal:

Find the minimum length of a contiguous subarray with sum greater than or equal to 7.

Step-by-step execution:

Result: min_length = 2
The shortest subarray is [4,3] with sum 7.

C++ Code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int current_sum = 0;
        int min_length = INT_MAX;

        for (int right = 0; right < nums.size(); ++right) {
            current_sum += nums[right];

            while (current_sum >= target) {
                min_length = min(min_length, right - left + 1);
                current_sum -= nums[left];
                left++;
            }
        }

        return (min_length != INT_MAX) ? min_length : 0;
    }
};