DSA

Minimum Size Subarray Sum

Covers: Brute Force, Sliding Window. Optimal — Time O(n), Space O(1).

August 8, 2026
DSAArraysLeetCodePracticePrefix SumSliding Window

Practice Link

Brute Force#

Try every possible starting index and extend the subarray rightward until the running sum meets or exceeds the target. For each valid window found, record its length and break early — extending further can only make it longer, not shorter. This is correct but slow because we restart the inner scan from scratch at every starting index, leading to O(n²) comparisons.

cpp
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();

        int miniLength=INT_MAX;

        for(int i=0;i<n;i++)
        {
            int sum = 0;
            for(int j=i;j<n;j++)
            {
                sum += nums[j];
                if(sum >= target){
                    miniLength = min(miniLength, j-i+1);
                    break;
                }
            }
        }
        if(miniLength==INT_MAX)
            return 0;
            
        return miniLength;
    }
};

Time Complexity: O(n^2), --> TLE

Space Complexity: O(1),

Sliding Window#

Instead of restarting from scratch at every index, we maintain a variable-length window with two pointers i (left) and j (right). Expand the window by advancing j when the sum is below the target; once the sum is satisfied, record the current window length and shrink it from the left by advancing i. Because each element is added at most once and removed at most once, the total work across all iterations is O(n) — a major improvement over the brute force approach.

cpp
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();

        int i =0,j=0, minLength = INT_MAX, sum=0;

        while(i<n || j<n)
        {
            if(sum >= target)
                minLength = min(minLength, j-i);

            if(j<n && sum<target){
                sum += nums[j];
                j++;
            }else{
                sum -= nums[i];
                i++;
            }
        }

        if(sum>=target)
            minLength = min(minLength, j-i);
            
        if(minLength==INT_MAX)
            return 0;

        return minLength;
    }
};

Time Complexity: O(n),

Space Complexity: O(1),

Related articles

DSASubarray Sum Equals KCovers: Brute Force, Prefix Sum, Optimal Single-Pass. Best — Time O(n), Space O(n).DSAContiguous ArrayCovers: Brute Force, Optimal Prefix Sum. Best — Time O(n), Space O(n).DSAMaximum Consecutive OnesOptimal approach. Optimal — Time O(n), Space O(1).