What is the brute force approach and complexity for Minimum Size Subarray Sum?

For each start, grow right until the sum reaches target with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Minimum Size Subarray Sum?

Grow right; while sum ≥ target, record the length and shrink from the left with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Minimum Size Subarray Sum?

Look for key signals in the prompt: "contiguous subarray" indicates The answer is a range [left … right] → think window.; "minimal length" indicates The window size is the answer, not an input → variable window. Shortest → record inside the shrink loop.; "sum ≥ target" indicates A sum can be updated in O(1) when one element enters or leaves.; "positive integers" indicates Adding only raises the sum, removing only lowers it. This is what makes shrinking from the left safe..

Minimum Size Subarray Sum

Medium·LeetCode #209Basic Anchor

LeetCode

Jump:

30-Second Mental ModelVariable Sliding Window (shortest valid)

Complexity:O(N²)→O(N)

Key Insight

Keep a window [left … right] and its sum. Move right forward one step at a time. Whenever the sum reaches target, the window is valid: record its length, then drop nums[left] to see if a shorter window still works. Keep shrinking while it stays valid.

Core Validity Invariant

The window is valid when sum ≥ target. Here, valid means "good enough to be an answer" — so we record it and then try to make it shorter.

Problem

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

Find the shortest contiguous subarray whose sum is at least target, and return its length. If no subarray reaches target, return 0.

Input

An integer target and an integer array nums.

Output

The length of the shortest subarray with sum ≥ target, or 0 if there is none.

Example 1

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

Output: 2

[4, 3] adds up to 7 and has length 2. No single element is 7 or more, so 2 is the shortest.

Example 2

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

Output: 1

The single element [4] already reaches 4.

Example 3

Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]

Output: 0

The whole array only adds up to 8, so nothing reaches 11.

Constraints

• 1 ≤ target ≤ 10^9
• 1 ≤ nums.length ≤ 10^5
• 1 ≤ nums[i] ≤ 10^4 (every number is positive)
• Follow-up: an O(N) solution exists; also try an O(N log N) one.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Is the answer a contiguous block or any set of elements?
2.
Is the size of the block given, or is the size what I'm looking for?
3.
If a block already has sum ≥ target, what happens to its sum if I make it longer? Do I care about longer blocks?
4.
If a block's sum is too small, can removing an element ever fix it?
5.
All numbers are positive. What does that guarantee about the sum when I add or remove an element?

Brute force approach

Idea

Pick every possible start. From that start, keep adding elements to the right until the sum reaches target. That gives the shortest valid subarray from that start. Take the smallest over all starts.

Thinking process

1
A subarray is decided by its start and end, so the simplest plan is to try them all.
2
From a fixed start, the sum only grows as the end moves right (numbers are positive).
3
So the first end where sum ≥ target is the shortest one for that start — stop there.
4
Keep the smallest length over all starts. If none worked, return 0.

Code & Implementation

brute.cpp

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

        // Try every start.
        for (int start = 0; start < n; start++) {
            long long sum = 0;
            // Grow the subarray to the right until its sum reaches target.
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum >= target) {
                    best = min(best, end - start + 1);
                    break; // a longer subarray from this start can't be shorter
                }
            }
        }
        return best == INT_MAX ? 0 : best;
    }
};

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

        // Try every start.
        for (int start = 0; start < n; start++) {
            long sum = 0;
            // Grow the subarray to the right until its sum reaches target.
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum >= target) {
                    best = Math.min(best, end - start + 1);
                    break; // a longer subarray from this start can't be shorter
                }
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        best = float("inf")

        # Try every start.
        for start in range(n):
            s = 0
            # Grow the subarray to the right until its sum reaches target.
            for end in range(start, n):
                s += nums[end]
                if s >= target:
                    best = min(best, end - start + 1)
                    break  # a longer subarray from this start can't be shorter

        return 0 if best == float("inf") else int(best)

export function minSubArrayLen(target: number, nums: number[]): number {
    const n = nums.length;
    let best = Infinity;

    // Try every start.
    for (let start = 0; start < n; start++) {
        let sum = 0;
        // Grow the subarray to the right until its sum reaches target.
        for (let end = start; end < n; end++) {
            sum += nums[end];
            if (sum >= target) {
                best = Math.min(best, end - start + 1);
                break; // a longer subarray from this start can't be shorter
            }
        }
    }
    return best === Infinity ? 0 : best;
}

Complexity

Time O(N²)Space O(1)

In the worst case (target bigger than the total), every start scans to the end: about N²/2 additions. With N = 10^5 that is 5·10^9 — too slow.

Better approach

Why brute force is slow

For each start, brute force walks right one element at a time until the sum is big enough. That walk can be N steps long.

What repeated work are we doing?

The same middle elements are added again and again, once for every start that passes over them.

What information can we reuse?

Store running totals once. Since they are sorted (all numbers positive), finding the right end becomes a binary search: O(log N) instead of O(N) per start.

New approach

Idea

Build prefix[i] = sum of the first i elements. The subarray nums[start … j−1] has sum prefix[j] − prefix[start]. We want the smallest j with prefix[j] ≥ prefix[start] + target. Because all numbers are positive, prefix is strictly increasing, so we can find that j with binary search (lower_bound).

Thinking process

1
Brute force adds the same elements again for every start.
2
With prefix sums, any range sum is one subtraction — but we still need to find where the end is.
3
Positive numbers mean prefix only goes up. A sorted array means binary search.
4
For each start, search for the first prefix value that is at least prefix[start] + target.

Code & Implementation

better.cpp

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

        // prefix[i] = sum of nums[0..i-1]. All numbers are positive,
        // so prefix is strictly increasing -> we can binary search it.
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int best = INT_MAX;
        for (int start = 0; start < n; start++) {
            // Smallest j with prefix[j] - prefix[start] >= target.
            long long need = prefix[start] + target;
            int j = lower_bound(prefix.begin(), prefix.end(), need) - prefix.begin();
            if (j <= n) {
                best = min(best, j - start); // subarray nums[start..j-1]
            }
        }
        return best == INT_MAX ? 0 : best;
    }
};

import java.util.Arrays;

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;

        // prefix[i] = sum of nums[0..i-1]. All numbers are positive,
        // so prefix is strictly increasing -> we can binary search it.
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int best = Integer.MAX_VALUE;
        for (int start = 0; start < n; start++) {
            // Smallest j with prefix[j] - prefix[start] >= target.
            long need = prefix[start] + target;
            int idx = Arrays.binarySearch(prefix, need);
            int j = idx >= 0 ? idx : -(idx + 1);
            if (j <= n) {
                best = Math.min(best, j - start); // subarray nums[start..j-1]
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

import bisect

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)

        # prefix[i] = sum of nums[0..i-1]. All numbers are positive,
        # so prefix is strictly increasing -> we can binary search it.
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        best = float("inf")
        for start in range(n):
            # Smallest j with prefix[j] - prefix[start] >= target.
            need = prefix[start] + target
            j = bisect.bisect_left(prefix, need)
            if j <= n:
                best = min(best, j - start)  # subarray nums[start..j-1]

        return 0 if best == float("inf") else int(best)

function lowerBound(arr: number[], target: number): number {
    let low = 0, high = arr.length;
    while (low < high) {
        const mid = (low + high) >> 1;
        if (arr[mid] >= target) high = mid;
        else low = mid + 1;
    }
    return low;
}

export function minSubArrayLen(target: number, nums: number[]): number {
    const n = nums.length;

    // prefix[i] = sum of nums[0..i-1]. All numbers are positive,
    // so prefix is strictly increasing -> we can binary search it.
    const prefix: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    let best = Infinity;
    for (let start = 0; start < n; start++) {
        // Smallest j with prefix[j] - prefix[start] >= target.
        const need = prefix[start] + target;
        const j = lowerBound(prefix, need);
        if (j <= n) {
            best = Math.min(best, j - start); // subarray nums[start..j-1]
        }
    }
    return best === Infinity ? 0 : best;
}

Complexity

Time O(N log N)Space O(N)

This is the follow-up the problem asks for. It is fast enough, but it needs an extra array and only works because the prefix array is sorted. The sliding window does it in O(N) with O(1) space.

Optimized approach

Idea

Start from brute force

Brute force fixes a start, walks right until the sum reaches target, then moves to the next start and begins again from zero.

Find the repeated work

When the start moves from i to i+1, the new subarray shares almost all of its elements with the old one. Worse, the end walks back over positions it already passed. Since the sum only got smaller, the new end must be at the same place or further right — so going back is pure waste.

Define the state — what variables do I need?

left: Start of the current window.
right: End of the current window. The element at right has just been added.
sum: Sum of nums[left … right].
best: Length of the shortest valid window seen so far (INT_MAX until we find one).

Define validity

The window is valid when sum ≥ target. Here, valid means "good enough to be an answer" — so we record it and then try to make it shorter.

Define the transitions — when does each pointer move, and why is it safe?

Every step

sum += nums[right]

The window grows by one element on the right. Growing is how we try to reach target.

While sum ≥ target

best = min(best, right − left + 1); sum −= nums[left]; left++

The window is valid, so its length is a candidate. Then we try a shorter one. Since numbers are positive, removing from the left only lowers the sum — once it drops below target, removing more can't help, so we stop and grow again.

At the end

return best == INT_MAX ? 0 : best

If the window was never valid, no subarray reaches target.

What does the current window add to the answer?

Every time the window is valid, its length right − left + 1 is a candidate for the shortest answer. We check it before shrinking, inside the while loop.

Code & Implementation

optimal.cpp

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int left = 0, best = INT_MAX;
        long long sum = 0; // sum of nums[left..right]

        for (int right = 0; right < n; right++) {
            sum += nums[right];            // 1. grow: nums[right] enters

            // 2. While the window is valid, record it, then try to make it shorter.
            //    The answer is updated INSIDE the loop because we want the shortest.
            while (sum >= target) {
                best = min(best, right - left + 1);
                sum -= nums[left];         // nums[left] leaves
                left++;
            }
        }
        return best == INT_MAX ? 0 : best;
    }
};

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, best = Integer.MAX_VALUE;
        long sum = 0; // sum of nums[left..right]

        for (int right = 0; right < n; right++) {
            sum += nums[right];            // 1. grow: nums[right] enters

            // 2. While the window is valid, record it, then try to make it shorter.
            //    The answer is updated INSIDE the loop because we want the shortest.
            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= nums[left];         // nums[left] leaves
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        left = 0
        best = float("inf")
        s = 0  # sum of nums[left..right]

        for right in range(n):
            s += nums[right]  # 1. grow: nums[right] enters

            # 2. While the window is valid, record it, then try to make it shorter.
            while s >= target:
                best = min(best, right - left + 1)
                s -= nums[left]  # nums[left] leaves
                left += 1

        return 0 if best == float("inf") else int(best)

export function minSubArrayLen(target: number, nums: number[]): number {
    const n = nums.length;
    let left = 0;
    let best = Infinity;
    let sum = 0; // sum of nums[left..right]

    for (let right = 0; right < n; right++) {
        sum += nums[right]; // 1. grow: nums[right] enters

        // 2. While the window is valid, record it, then try to make it shorter.
        //    The answer is updated INSIDE the loop because we want the shortest.
        while (sum >= target) {
            best = Math.min(best, right - left + 1);
            sum -= nums[left]; // nums[left] leaves
            left++;
        }
    }
    return best === Infinity ? 0 : best;
}

Complexity

Time O(N)Space O(1)

There is a while inside a for, but left only moves forward and can move at most N times in total. So the total work is at most 2N steps.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each start, grow right until the sum reaches target	O(N²)	O(1)
Better	Running totals are sorted, so binary search the end for each start	O(N log N)	O(N)
Optimal	Grow right; while sum ≥ target, record the length and shrink from the left	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous subarray”The answer is a range [left … right] → think window.
“minimal length”The window size is the answer, not an input → variable window. Shortest → record inside the shrink loop.
“sum ≥ target”A sum can be updated in O(1) when one element enters or leaves.
“positive integers”Adding only raises the sum, removing only lowers it. This is what makes shrinking from the left safe.

Contiguous range+minimum length+sum ≥ target+all numbers positive→Variable Sliding Window (shortest valid)

This is the anchor for variable windows. The rule is simple (sum ≥ target), so you can focus on the shape: grow right every step, shrink left while you can. It is the shortest version: you shrink while the window is valid and record the answer inside the loop. Most other questions in this group ask for the longest window, where you shrink while it is invalid and record after the loop.

Don't make this mistake

Recording the answer outside the while loop

✗ while (sum >= target) { sum -= nums[left]; left++; } best = min(best, right - left + 1);

✓ while (sum >= target) { best = min(best, right - left + 1); sum -= nums[left]; left++; }

After the loop ends, the window is invalid (sum < target). Recording it would give a length that is too short and doesn't reach target. For shortest windows, record while the window is still valid.

Using `if` instead of `while` to shrink

✗ if (sum >= target) { ... left++; }

✓ while (sum >= target) { ... left++; }

After adding one big number, you may be able to drop several small ones from the left. An if drops only one and misses shorter answers.

Returning INT_MAX when there is no answer

✗ return best;

✓ return best == INT_MAX ? 0 : best;

The problem says to return 0 when no subarray reaches target.

Using this window when numbers can be negative

If negatives are allowed, removing an element from the left could increase the sum, so stopping the shrink early might skip a valid shorter window. The window only works because every number is positive. With negatives, you need prefix sums with a monotonic deque (LeetCode 862).

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Subarray with Given Sum (non-negative numbers)