Log inSign up
mediumLeetCodeNot Started

Minimum Size Subarray Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length of 2 with sum 7 >= 7.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1
Explanation: The subarray [4] has minimal length 1 with sum 4 >= 4.

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 valid subarray exists.

Constraints:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window & Two Pointers technique
  • Prefix sums and monotonic array properties
  • Binary search on monotonically increasing prefix arrays

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the shrinking sliding window pattern for minimization problems.
  • Understand why strictly positive numbers guarantee monotonic sum properties.
  • Implement the O(N log N) prefix sum + binary search alternative solution.
  • Differentiate between "at least K" with positive numbers vs negative numbers.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding the shortest/minimal length contiguous subarray satisfying a sum condition (sum >= target).
  • All array elements are strictly positive (nums[i] >= 1).
  • Dynamic window that shrinks upon becoming valid.

Algorithmic Decision Tree:

  • If elements contain negative values -> Cannot use sliding window; use Monotonic Deque + Prefix Sums in O(N) (Shortest Subarray with Sum at Least K).
  • If elements are strictly positive -> Two-Pointer Sliding Window in O(N) time and O(1) space.
  • If follow-up asks for O(N log N) -> Prefix Sums + Binary Search.

Connected Patterns:

Shortest Subarray with Sum at Least K (handles negative numbers with Deque)Subarray Product Less Than KMinimum Operations to Reduce X to Zero

1. Brute Force (Nested Loop Subarray Sum)

Intuition

Fix starting index i. Expand rightwards with index j, accumulating sum += nums[j]. As soon as sum >= target, update minLen = min(minLen, j - i + 1) and break.

Algorithm

  1. Step 1: Initialize minLen = Infinity.
  2. Step 2: For each i from 0 to n - 1:
  3. - Initialize sum = 0.
  4. - For each j from i to n - 1:
  5. - sum += nums[j].
  6. - If sum >= target: minLen = min(minLen, j - i + 1), break.
  7. Step 3: Return minLen == Infinity ? 0 : minLen.

All Subarrays Enumeration (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
First subarray from start reaching target 7 has length 4
Visual state
Values and pointers at this exact step
pointers
S
2
3
1
2
4
3
0
↑ i
1
2
3
↑ j
4
5
Variables at this step
start
0
end
3
sum
8
len
4
minLen
4
Check / comparison
Subarray [0..3]: 2 + 3 + 1 + 2 = 8 >= 7
Decision / next transition
Valid sum! Length = 4. Set minLen = 4.
Why this step matters

First subarray from start reaching target 7 has length 4.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int minSubArrayLen(int target, std::vector<int>& nums) {
8 int n = nums.size();
9 int minLen = n + 1;
10
11 for (int i = 0; i < n; i++) {
12 int sum = 0;
13 for (int j = i; j < n; j++) {
14 sum += nums[j];
15 if (sum >= target) {
16 minLen = std::min(minLen, j - i + 1);
17 break;
18 }
19 }
20 }
21 return minLen > n ? 0 : minLen;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::vector<int> nums = {2, 3, 1, 2, 4, 3};
28 std::cout << "Min Length: " << sol.minSubArrayLen(7, nums) << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Nested Loop Subarray Sum).
  • Space complexity: O(1) — Space complexity for Brute Force (Nested Loop Subarray Sum).

Why Brute Force Doesn't Scale:

For N = 100,000, quadratic brute force takes 1010 operations (> 10s). The two-pointer sliding window runs in strict O(N) time with at most 200,000 pointer movements (< 3 ms).

For N = 100,000: Brute force takes ~10 billion operations; Sliding window takes ~200,000 operations (~50,000x faster).

2. Better (Prefix Sums + Binary Search)

Intuition

Since all numbers are positive, prefix[k] = sum(nums[0...k-1]) is strictly increasing. For a starting index i, we need prefix[j] - prefix[i] >= target -> prefix[j] >= prefix[i] + target. We binary search for j using lower_bound in O(log N).

Algorithm

  1. Step 1: Construct prefix sum array prefix of size n + 1 where prefix[i] = prefix[i-1] + nums[i-1].
  2. Step 2: Initialize minLen = Infinity.
  3. Step 3: For each i from 0 to n:
  4. - Binary search in prefix for the smallest j such that prefix[j] >= prefix[i] + target.
  5. - If found, minLen = min(minLen, j - i).
  6. Step 4: Return minLen == Infinity ? 0 : minLen.

Prefix Sums + Binary Search (O(N log N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Monotonicity of prefix sums is key to binary search
Visual state
Values and pointers at this exact step
pointers
S
0
2
5
6
8
12
15
0
↑ P
1
2
3
4
5
6
Variables at this step
prefix
[0,2,5,6,8,12,15]
minLen
null
Check / comparison
Build prefix sums P: [0, 2, 5, 6, 8, 12, 15]
Decision / next transition
Since nums[i] > 0, P is strictly increasing, enabling binary search.
Why this step matters

Monotonicity of prefix sums is key to binary search.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int minSubArrayLen(int target, std::vector<int>& nums) {
8 int n = nums.size();
9 std::vector<long long> prefix(n + 1, 0);
10 for (int i = 0; i < n; i++) {
11 prefix[i + 1] = prefix[i] + nums[i];
12 }
13
14 int minLen = n + 1;
15 for (int i = 0; i < n; i++) {
16 long long needed = prefix[i] + target;
17 auto it = std::lower_bound(prefix.begin() + i + 1, prefix.end(), needed);
18 if (it != prefix.end()) {
19 int j = std::distance(prefix.begin(), it);
20 minLen = std::min(minLen, j - i);
21 }
22 }
23 return minLen > n ? 0 : minLen;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::vector<int> nums = {2, 3, 1, 2, 4, 3};
30 std::cout << "BS Min Length: " << sol.minSubArrayLen(7, nums) << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Prefix Sums + Binary Search).
  • Space complexity: O(N) — Space complexity for Better (Prefix Sums + Binary Search).

3. Optimal (Two-Pointer Sliding Window)

Intuition

1. Initialize left = 0, windowSum = 0, minLen = Infinity. 2. Iterate right from 0 to n - 1: - windowSum += nums[right] - While windowSum >= target: - minLen = min(minLen, right - left + 1) - windowSum -= nums[left] - left++ 3. Return minLen == Infinity ? 0 : minLen.

Algorithm

  1. Step 1: Initialize left = 0, windowSum = 0, and minLen = Infinity.
  2. Step 2: For right from 0 to nums.length - 1:
  3. - Add nums[right] to windowSum.
  4. - While windowSum >= target:
  5. - minLen = min(minLen, right - left + 1).
  6. - Subtract nums[left] from windowSum.
  7. - left++.
  8. Step 3: Return minLen == Infinity ? 0 : minLen.

Dynamic Sliding Window (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
The window reaches target threshold at R = 3
Visual state
Values and pointers at this exact step
pointers
S
2
3
1
2
4
3
0
↑ L
1
2
3
↑ R
4
5
Variables at this step
L
0
R
3
sum
8
minLen
4
Check / comparison
Expand R from 0 to 3: sum = 2 + 3 + 1 + 2 = 8 >= 7
Decision / next transition
Sum >= 7! Window length = 4. Record minLen = 4. Shrink L.
Why this step matters

The window reaches target threshold at R = 3.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int minSubArrayLen(int target, std::vector<int>& nums) {
8 int n = nums.size();
9 int left = 0;
10 long long windowSum = 0;
11 int minLen = n + 1;
12
13 for (int right = 0; right < n; right++) {
14 windowSum += nums[right];
15
16 while (windowSum >= target) {
17 minLen = std::min(minLen, right - left + 1);
18 windowSum -= nums[left];
19 left++;
20 }
21 }
22 return minLen > n ? 0 : minLen;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::vector<int> nums = {2, 3, 1, 2, 4, 3};
29 std::cout << "Optimal Min Length: " << sol.minSubArrayLen(7, nums) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (Two-Pointer Sliding Window).
  • Space complexity: O(1) — Space complexity for Optimal (Two-Pointer Sliding Window).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Nested Loop Subarray Sum)O(N^2)O(1)For each starting index i, expand j and accumulate sum. As soon as sum >= target, record length j - i + 1 and break.Repeatedly summing overlapping elements from scratch.
2.Better (Prefix Sums + Binary Search)O(N log N)O(N)Build prefix sums array (strictly increasing). For each prefix[i], binary search for the first prefix[j] where prefix[j] >= prefix[i] + target.Binary search over prefix sums for each index.
3.Optimal (Two-Pointer Sliding Window)OptimalO(N)O(1)Expand right pointer, and while windowSum >= target, record minLen and shrink left pointer.Single pass scan bound.

Common Pitfalls & Crucial Edge Cases

Returning `Infinity` or `n + 1` instead of `0` when no solution exists

Always check if minLen was never updated.

Attempting sliding window on arrays with negative numbers

If elements can be negative, adding elements can decrease the sum and removing elements can increase the sum, breaking sliding window monotonicity (requiring a monotonic deque instead).

Updating `minLen` outside the while loop

If multiple valid windows can be formed while shrinking left, updating outside the while loop misses shorter valid subwindows.

Crucial Edge Cases to Validate:

  • Total sum < target (nums = [1, 1, 1], target = 10): Loop finishes without windowSum ever reaching target; returns 0.
  • Single element >= target (nums = [1, 4, 4], target = 4): Immediately finds length 1, returns 1.
  • Entire array equals target (nums = [1, 2, 3], target = 6): Returns n = 3.
  • Large target with large array (target = 10^9): Handled safely with 64-bit integer accumulation.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether all numbers are positive: if yes, two pointers is optimal O(N) time and O(1) space; if numbers can be negative, mention LeetCode 862 (Monotonic Deque).
  2. State the binary search alternative O(N log N) using prefix sums, as interviewers frequently ask for this specific follow-up.
  3. Remember the default return value is 0 (not -1 or Infinity).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the Sliding Window approach guarantee O(N) time complexity for Minimum Size Subarray Sum?

2.Why would the Two-Pointer Sliding Window approach fail if the array contained negative numbers?

3.What is the return value if sum(nums) < target?

Back to DSA Sheet