Minimum Size Subarray Sum
Last Updated: March 21, 2026
Understanding the Problem
We're looking for the shortest contiguous subarray whose elements sum to at least target. Two things jump out right away.
First, the array contains only positive integers. That's a huge deal. It means that as we extend a subarray to the right, the sum can only increase. And as we shrink it from the left, the sum can only decrease. This monotonic behavior is exactly what makes the sliding window technique work here.
Second, we want the minimum length, not the subarray itself. So we just need to track the best length seen so far as we scan through the array.
Key Constraints:
nums.lengthup to10^5means O(n^2) is borderline. It might pass with a tight constant factor, but we should aim for O(n) or O(n log n).- All values are positive (both
nums[i]andtarget). This guarantees that prefix sums are strictly increasing, which unlocks binary search. It also means the sliding window's sum behaves monotonically. targetcan be up to10^9andnums[i]up to10^4, so even summing all10^5elements gives at most10^9. There are valid cases where no subarray meets the target.
Approach 1: Brute Force
Intuition
The most straightforward approach is to check every possible subarray. For each starting index i, extend the subarray to the right, accumulating the sum. The moment the sum reaches target, record the length and move on to the next starting index. Since we want the minimum, we can break early for each i once we find a valid subarray starting there (the first valid one for a given i is the shortest for that start, because we're extending one element at a time).
Algorithm
- Initialize
minLento infinity (orn + 1as a sentinel). - For each starting index
ifrom0ton - 1: - Initialize a running sum to
0. - For each ending index
jfromiton - 1: - Add
nums[j]to the running sum. - If the sum >=
target, updateminLen = min(minLen, j - i + 1)and break. - If
minLenis still the sentinel, return0. Otherwise returnminLen.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the
nstarting indices, we may scan up tonelements in the worst case. With the early break, the best case is better, but worst case remains quadratic. - Space Complexity: O(1). We only use a few variables regardless of input size.
The brute force re-scans elements from scratch for every starting index. But if the subarray [i..j] has sum >= target, then when we move to i + 1, the right boundary can only stay the same or move right. Can we avoid resetting the right pointer?
Approach 2: Sliding Window
Intuition
Since all elements are positive, adding an element to the window increases the sum and removing one decreases it. This monotonic behavior means we can use a sliding window with two pointers.
The idea is simple. Expand the window by moving the right pointer forward, adding elements to the running sum. Once the sum reaches or exceeds target, we've found a valid window, but it might not be the shortest. So we try shrinking it from the left: subtract nums[left], advance left, and check if the window is still valid. We keep shrinking as long as the sum stays >= target, updating the minimum length each time.
Every element enters the window once (when right advances) and leaves once (when left advances). That's at most 2n operations total, giving us O(n).
The key insight is that both pointers only move forward. The right pointer advances one step per outer loop iteration, and the left pointer never moves backward. Since all elements are positive, moving right always increases the sum and moving left always decreases it. This means we never miss a valid window: if a shorter valid window exists, we'll find it when we shrink past the current left boundary.
Each element is added to currentSum exactly once (when right reaches it) and subtracted exactly once (when left passes it). So the total work across all iterations of both the outer loop and the inner while loop is O(n).
Algorithm
- Initialize
left = 0,currentSum = 0, andminLen = n + 1. - Iterate
rightfrom0ton - 1: - Add
nums[right]tocurrentSum. - While
currentSum >= target: - Update
minLen = min(minLen, right - left + 1). - Subtract
nums[left]fromcurrentSum. - Increment
left. - Return
0ifminLenis still the sentinel, otherwise returnminLen.
Example Walkthrough
Code
- Time Complexity: O(n). Each element is visited at most twice, once by
rightand once byleft. The inner while loop doesn't make this quadratic becauseleftmoves at mostntimes total across all iterations. - Space Complexity: O(1). Only a constant number of variables are used.
The sliding window is already optimal at O(n) time and O(1) space. But the problem's follow-up asks for an O(n log n) solution using a different technique: prefix sums combined with binary search.
Approach 3: Prefix Sum + Binary Search
Intuition
Here's a different angle. If we build a prefix sum array where prefix[i] is the sum of the first i elements, then the sum of the subarray from index i to j is prefix[j + 1] - prefix[i]. We want that difference to be >= target, which means for each index i, we need to find the smallest j such that prefix[j + 1] >= prefix[i] + target.
Since all elements are positive, the prefix sum array is strictly increasing. A strictly increasing array is sorted, which means we can binary search for the value prefix[i] + target in the prefix array. This gives us the left boundary of the smallest valid window starting at index i.
The prefix sum converts the "subarray sum" problem into a "difference between two prefix values" problem. Since all elements are positive, the prefix array is strictly increasing. That sorted property lets us binary search for the target threshold instead of linearly scanning, turning what would be O(n) per starting index into O(log n) per starting index.
Algorithm
- Build a prefix sum array of size
n + 1whereprefix[0] = 0andprefix[i] = prefix[i-1] + nums[i-1]. - Initialize
minLen = n + 1. - For each index
ifrom0ton: - Binary search in
prefixfor the smallest indexjwhereprefix[j] >= prefix[i] + target. - If such a
jexists andj <= n, updateminLen = min(minLen, j - i). - Return
0ifminLenis still the sentinel, otherwise returnminLen.
Example Walkthrough
Code
- Time Complexity: O(n log n). Building the prefix sum array takes O(n). For each of the
n + 1starting positions, we perform a binary search over at mostnelements, taking O(log n) each. Total: O(n) + O(n log n) = O(n log n). - Space Complexity: O(n). The prefix sum array requires O(n) additional space.