Minimum Size Subarray Sum

Description

You are given an array of positive integers nums and a positive integer target. Your task is to find the smallest contiguous subarray whose elements sum up to at least target (i.e., the sum is greater than or equal to target). Return the length of that subarray. If no such subarray exists, return 0.

A subarray is a contiguous, non-empty sequence of elements within the array. For example, in [2, 3, 1, 2, 4, 3], the subarray [3, 1, 2] starts at index 1 and ends at index 3.

Examples

Example 1

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

Output: 2

Explanation: We need a contiguous subarray whose sum is at least 7. The subarray [4, 3] has a sum of 7, and its length is 2. No single element reaches 7, so length 1 is not possible. Therefore the minimal length is 2.

Example 2

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

Output: 1

Explanation: The element 4 at index 1 (or index 2) alone is already greater than or equal to 4. A single element forms a valid subarray with length 1, which is the smallest possible.

Example 3

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

Output: 0

Explanation: The total sum of all elements is 8, which is less than 11. No subarray can reach the target, so we return 0.

Constraints

1 ≤ target ≤ 10^9
1 ≤ nums.length ≤ 10^5
1 ≤ nums[i] ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to consider every possible subarray and check if its sum meets the target. For each starting index, we extend the subarray one element at a time, keeping a running sum. As soon as the running sum reaches or exceeds the target, we record the length and stop extending from that starting point (since adding more elements would only make it longer, not shorter).

Think of it like measuring rope from a spool: you pick a starting point, keep pulling out more rope until you have enough length (sum ≥ target), record how much you pulled, then start again from the next point on the spool.

Step-by-Step Explanation

Let's trace through with target = 7, nums = [2, 3, 1, 2, 4, 3]:

Step 1: Initialize min_length = infinity (we haven't found any valid subarray yet).

Step 2: Start with i=0. Running sum = 0.

Add nums[0]=2: sum=2. Is 2 ≥ 7? No.
Add nums[1]=3: sum=5. Is 5 ≥ 7? No.
Add nums[2]=1: sum=6. Is 6 ≥ 7? No.
Add nums[3]=2: sum=8. Is 8 ≥ 7? Yes! Length = 3-0+1 = 4. Update min_length = 4.

Step 3: Start with i=1. Running sum = 0.

Add nums[1]=3: sum=3. Is 3 ≥ 7? No.
Add nums[2]=1: sum=4. Is 4 ≥ 7? No.
Add nums[3]=2: sum=6. Is 6 ≥ 7? No.
Add nums[4]=4: sum=10. Is 10 ≥ 7? Yes! Length = 4-1+1 = 4. min_length stays 4.

Step 4: Start with i=2. Running sum = 0.

Add nums[2]=1: sum=1. Not enough.
Add nums[3]=2: sum=3. Not enough.
Add nums[4]=4: sum=7. Is 7 ≥ 7? Yes! Length = 4-2+1 = 3. Update min_length = 3.

Step 5: Start with i=3. Running sum = 0.

Add nums[3]=2: sum=2. Not enough.
Add nums[4]=4: sum=6. Not enough.
Add nums[5]=3: sum=9. Is 9 ≥ 7? Yes! Length = 5-3+1 = 3. min_length stays 3.

Step 6: Start with i=4. Running sum = 0.

Add nums[4]=4: sum=4. Not enough.
Add nums[5]=3: sum=7. Is 7 ≥ 7? Yes! Length = 5-4+1 = 2. Update min_length = 2.

Step 7: Start with i=5. Running sum = 0.

Add nums[5]=3: sum=3. Not enough. Reached end. No valid subarray from i=5.

Result: min_length = 2.

Brute Force — Trying All Starting Positions — Watch how we try every starting index and extend rightward until the running sum reaches the target, then record the subarray length.

Algorithm

Initialize min_length to infinity (or n+1) to track the shortest valid subarray
For each starting index i from 0 to n-1:
- Initialize a running sum to 0
- For each ending index j from i to n-1:
  - Add nums[j] to sum
  - If sum ≥ target:
    - Update min_length = min(min_length, j - i + 1)
    - Break the inner loop (extending further only increases length)
If min_length is still infinity, return 0 (no valid subarray found)
Otherwise, return min_length

Code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int minLen = 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) {
                    minLen = min(minLen, j - i + 1);
                    break;
                }
            }
        }
        
        return minLen == INT_MAX ? 0 : minLen;
    }
};

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        min_len = float('inf')
        
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                if current_sum >= target:
                    min_len = min(min_len, j - i + 1)
                    break
        
        return 0 if min_len == float('inf') else min_len

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

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and for each starting index, the inner loop can run up to n times in the worst case (when no subarray starting from that index reaches the target). This gives us n × n = O(n²) operations in total.

Space Complexity: O(1)

We only use a few integer variables (min_len, sum, loop counters). No additional data structures that grow with input size are needed.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity. With the constraint that nums.length can be up to 10^5, this means up to 10^10 operations in the worst case — far too slow for typical time limits of 1-2 seconds.

The core inefficiency is redundant computation: when we move the starting index from i to i+1, we throw away all the summation work we did and start adding from scratch. We're not reusing any information from previous iterations.

Key insight: instead of restarting the sum for every new starting point, what if we maintained a window and adjusted both ends intelligently? If the current window's sum is large enough, we can try shrinking from the left. If it's too small, we extend from the right. This way, each element is added and removed at most once, giving us O(n) total work.

Better Approach - Prefix Sum with Binary Search

Intuition

Before jumping to the optimal O(n) sliding window, there is an elegant O(n log n) approach that uses prefix sums and binary search.

The key observation is: if we precompute prefix sums, then the sum of any subarray nums[i..j] equals prefix[j+1] - prefix[i]. We want this to be ≥ target, i.e., prefix[j+1] ≥ prefix[i] + target.

Since all elements are positive, the prefix sum array is strictly increasing. This monotonicity lets us use binary search: for each starting index i, we binary search for the smallest j such that prefix[j] ≥ prefix[i] + target. The distance j - i gives us the subarray length.

Think of it like reading a water meter: the prefix sum is the running total, and you're looking for the earliest point where the meter reading has increased by at least target from your starting reading.

Step-by-Step Explanation

Let's trace through with target = 7, nums = [2, 3, 1, 2, 4, 3]:

Step 1: Build prefix sum array.

prefix = [0, 2, 5, 6, 8, 12, 15]
prefix[0] = 0 (empty prefix)
prefix[1] = 2, prefix[2] = 5, prefix[3] = 6, prefix[4] = 8, prefix[5] = 12, prefix[6] = 15

Step 2: For i=0: We need prefix[j] ≥ prefix[0] + 7 = 0 + 7 = 7.

Binary search in prefix[1..6] for the first value ≥ 7.
prefix = [0, 2, 5, 6, 8, 12, 15]. Found at index 4.
Length = 4 - 0 = 4. min_length = 4.

Step 3: For i=1: We need prefix[j] ≥ prefix[1] + 7 = 2 + 7 = 9.

Binary search for first value ≥ 9.
prefix = [0, 2, 5, 6, 8, 12, 15]. Found at index 5.
Length = 5 - 1 = 4. min_length stays 4.

Step 4: For i=2: We need prefix[j] ≥ prefix[2] + 7 = 5 + 7 = 12.

Binary search for first value ≥ 12.
prefix = [0, 2, 5, 6, 8, 12, 15]. Found at index 5.
Length = 5 - 2 = 3. Update min_length = 3.

Step 5: For i=3: We need prefix[j] ≥ prefix[3] + 7 = 6 + 7 = 13.

Binary search for first value ≥ 13.
prefix = [0, 2, 5, 6, 8, 12, 15]. Found at index 6.
Length = 6 - 3 = 3. min_length stays 3.

Step 6: For i=4: We need prefix[j] ≥ prefix[4] + 7 = 8 + 7 = 15.

Binary search for first value ≥ 15.
prefix = [0, 2, 5, 6, 8, 12, 15]. Found at index 6.
Length = 6 - 4 = 2. Update min_length = 2.

Step 7: For i=5: We need prefix[j] ≥ prefix[5] + 7 = 12 + 7 = 19.

Binary search for first value ≥ 19.
Not found (max is 15). No valid subarray from i=5.

Step 8: For i=6: We need prefix[j] ≥ prefix[6] + 7 = 15 + 7 = 22.

Not found. No valid subarray from i=6.

Result: min_length = 2.

Prefix Sum + Binary Search — Finding Shortest Subarray — Watch how we use the prefix sum array to convert subarray sum queries into binary search lookups, finding the shortest valid subarray efficiently.

Algorithm

Build a prefix sum array of size n+1, where prefix[0] = 0 and prefix[k] = prefix[k-1] + nums[k-1]
Initialize min_length to infinity
For each starting index i from 0 to n:
- Compute needed = prefix[i] + target
- Use binary search (lower_bound) to find the smallest index j in prefix where prefix[j] ≥ needed
- If such j exists and j ≤ n:
  - Update min_length = min(min_length, j - i)
Return min_length if it's not infinity, otherwise return 0

Code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int minLen = INT_MAX;
        vector<int> prefix(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        
        for (int i = 0; i <= n; i++) {
            int needed = prefix[i] + target;
            auto it = lower_bound(prefix.begin(), prefix.end(), needed);
            if (it != prefix.end()) {
                int j = it - prefix.begin();
                minLen = min(minLen, j - i);
            }
        }
        
        return minLen == INT_MAX ? 0 : minLen;
    }
};

import bisect

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        min_len = float('inf')
        prefix = [0] * (n + 1)
        
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + nums[i - 1]
        
        for i in range(n + 1):
            needed = prefix[i] + target
            j = bisect.bisect_left(prefix, needed)
            if j <= n:
                min_len = min(min_len, j - i)
        
        return 0 if min_len == float('inf') else min_len

import java.util.Arrays;

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;
        int[] prefix = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        
        for (int i = 0; i <= n; i++) {
            int needed = prefix[i] + target;
            int j = Arrays.binarySearch(prefix, needed);
            if (j < 0) j = -(j + 1);
            if (j <= n) {
                minLen = Math.min(minLen, j - i);
            }
        }
        
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Building the prefix sum array takes O(n). For each of the n+1 starting positions, we perform a binary search over the prefix array of size n+1, which takes O(log n) per search. Total: O(n) + O(n log n) = O(n log n).

Space Complexity: O(n)

We store the prefix sum array of size n+1, which uses O(n) extra space.

Why This Approach Is Not Efficient

The prefix sum + binary search approach improves from O(n²) to O(n log n), which is a significant speedup. For n = 10^5, this is about 1.7 × 10^6 operations — well within time limits.

However, we can do even better. The binary search approach doesn't fully exploit the sequential nature of the problem. When we move the starting index from i to i+1, the previous answer gives us information about where the ending index might be — but we throw that away and binary search from scratch.

Since all elements are positive, as we move the start forward, the required end position can only move forward or stay the same (never backward). This monotonic relationship means we can use a sliding window where both pointers only advance, giving us O(n) amortized time.

Optimal Approach - Sliding Window

Intuition

The sliding window technique takes advantage of a crucial property: all elements in nums are positive. This means:

Expanding the window (moving the right end forward) always increases the sum.
Shrinking the window (moving the left end forward) always decreases the sum.

We maintain two pointers, left and right, defining a window [left, right]. We expand by moving right to add elements until the window sum reaches the target. Once it does, we try to shrink from the left, because maybe we don't need all those elements — perhaps a shorter suffix of the current window also has a sum ≥ target.

Imagine you're collecting rainwater in a bucket. You keep adding cups of water (expanding) until you have enough. Then you start pouring out from the other side (shrinking), checking if you still have enough. The smallest number of cups that still gives you enough water is your answer.

Step-by-Step Explanation

Let's trace through with target = 7, nums = [2, 3, 1, 2, 4, 3]:

Step 1: Initialize left=0, sum=0, min_length = infinity.

Step 2: Expand: right=0, add nums[0]=2. sum=2. Is 2 ≥ 7? No. Continue expanding.

Step 3: Expand: right=1, add nums[1]=3. sum=5. Is 5 ≥ 7? No. Continue expanding.

Step 4: Expand: right=2, add nums[2]=1. sum=6. Is 6 ≥ 7? No. Continue expanding.

Step 5: Expand: right=3, add nums[3]=2. sum=8. Is 8 ≥ 7? Yes!

Window [0..3] has length 4. Update min_length = 4.
Try shrinking: remove nums[0]=2. sum=6. Is 6 ≥ 7? No. Stop shrinking. left=1.

Step 6: Expand: right=4, add nums[4]=4. sum=10. Is 10 ≥ 7? Yes!

Window [1..4] has length 4. min_length stays 4.
Shrink: remove nums[1]=3. sum=7. Is 7 ≥ 7? Yes!
Window [2..4] has length 3. Update min_length = 3.
Shrink: remove nums[2]=1. sum=6. Is 6 ≥ 7? No. Stop shrinking. left=3.

Step 7: Expand: right=5, add nums[5]=3. sum=9. Is 9 ≥ 7? Yes!

Window [3..5] has length 3. min_length stays 3.
Shrink: remove nums[3]=2. sum=7. Is 7 ≥ 7? Yes!
Window [4..5] has length 2. Update min_length = 2.
Shrink: remove nums[4]=4. sum=3. Is 3 ≥ 7? No. Stop shrinking. left=5.

Step 8: right has reached end. Done. Return min_length = 2.

Sliding Window — Expand and Shrink to Find Minimum Subarray — Watch how the window expands rightward until the sum is large enough, then shrinks from the left to find the shortest valid subarray, before expanding again.

Algorithm

Initialize left = 0, sum = 0, min_length = infinity
For each right from 0 to n-1:
- Add nums[right] to sum
- While sum ≥ target:
  - Update min_length = min(min_length, right - left + 1)
  - Subtract nums[left] from sum
  - Increment left
Return min_length if it's not infinity, otherwise return 0

Code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int sum = 0;
        int minLen = INT_MAX;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            while (sum >= target) {
                minLen = min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        
        return minLen == INT_MAX ? 0 : minLen;
    }
};

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        left = 0
        current_sum = 0
        min_len = float('inf')
        
        for right in range(n):
            current_sum += nums[right]
            
            while current_sum >= target:
                min_len = min(min_len, right - left + 1)
                current_sum -= nums[left]
                left += 1
        
        return 0 if min_len == float('inf') else min_len

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Complexity Analysis

Time Complexity: O(n)

Although there is a while loop inside the for loop, each element is added to the window at most once (when right advances) and removed at most once (when left advances). The left pointer only moves forward and can advance at most n times total across the entire algorithm. Therefore, the total number of operations is at most 2n, which is O(n).

Space Complexity: O(1)

We only use a fixed number of integer variables (left, sum, minLen). No additional data structures are needed, regardless of input size.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Minimum Size Subarray Sum

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Prefix Sum with Binary Search

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Sliding Window

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis