Minimum Size Subarray Sum
Understanding the Problem
We're looking for the shortest contiguous subarray whose elements sum to at least target. Two properties of the input shape the solution.
First, the array contains only positive integers. 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 what makes the sliding window technique work here.
Second, we want the minimum length, not the subarray itself, so we only track the best length seen so far as we scan through the array.
Key Constraints:
nums.lengthup to10^5rules out a comfortable O(n^2) scan, so we 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 is what makes binary search applicable. It also means the sliding window's sum behaves monotonically. targetcan be up to10^9andnums[i]up to10^4, so the sum of all10^5elements reaches10^9. A subarray sum plustargetcan approach2 * 10^9, which is close to the 32-bit integer limit. There are also valid cases where no subarray meets the target.
Approach 1: Brute Force
Intuition
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. We break early for each i once we find a valid subarray starting there: because we extend one element at a time, the first valid subarray for a given start is also the shortest for that start.
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. When the subarray [i..j] already meets the target, moving the start to i + 1 can only require a right boundary that stays the same or moves further right, never one that moves left. The next approach exploits this to 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 lets us maintain a single window with two pointers instead of restarting at every index.
Expand the window by moving the right pointer forward, adding each new element to a running sum. Once the sum reaches target, the window is valid but possibly longer than necessary, so shrink it from the left: subtract nums[left], advance left, and continue while the sum stays at or above target, updating the minimum length on each valid window.
The window never misses the shortest valid subarray. For a fixed right boundary, shrinking from the left stops at the first position where the sum drops below target, so the window recorded is the shortest one ending at that right. Because positivity makes the sum monotonic in both pointers, once left passes a position it can never need to return: a smaller left only produces a longer window with a larger sum. Taking the minimum over every right boundary therefore covers every candidate.
Each element is added to currentSum once (when right reaches it) and subtracted at most once (when left passes it). The inner while loop advances left a total of at most n times across the whole run, so the algorithm performs at most 2n operations.
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 optimal at O(n) time and O(1) space, so for this problem there is no need to look further. The follow-up asks for an O(n log n) solution, and the prefix-sum-plus-binary-search approach below answers it. It is worth seeing for a reason beyond the follow-up: the sliding window depends on every element being positive, while the prefix-sum approach can be adapted to arrays that contain negative numbers, where shrinking from the left no longer reduces the sum predictably.
Approach 3: Prefix Sum + Binary Search
Intuition
Build a prefix sum array where prefix[i] is the sum of the first i elements. The sum of the subarray from index i to j is then prefix[j + 1] - prefix[i]. For that difference to be at least target, we need prefix[j + 1] >= prefix[i] + target, so for each start index i we search for the smallest end index whose prefix value reaches that threshold.
Since all elements are positive, the prefix sum array is strictly increasing, and a strictly increasing array is sorted. We can binary search it for the value prefix[i] + target, which gives the right boundary of the smallest valid window starting at index i.
Binary search needs a sorted array, and the prefix array is sorted only because every element is positive. With negative numbers present, prefix sums can decrease, the array is no longer sorted, and this exact technique breaks. The fix for that case keeps prefix sums but replaces the binary search with a monotonic deque (the approach used in "Shortest Subarray with Sum at Least K"). For an all-positive input, the sorted prefix array is what reduces each start's search from a linear scan to O(log n).
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.