Minimum Size Subarray Sum
Medium · rating 1500 · Sliding Window, Two Pointers
The first line has n and target t. The second line has n positive integers. Print the length of the shortest contiguous subarray whose sum is at least t, or 0 if none exists.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Because all values are positive, a sliding window works: expand the right edge to grow the sum, and whenever the sum reaches the target, shrink from the left as far as possible while recording the window length. The shortest qualifying window is the answer.
Why shrinking is valid
Adding elements only increases the sum, so once the target is met, pulling in the left edge finds the tightest window ending at the current right edge.
i = cur = 0; best = inf
for j in range(n):
cur += a[j]
while cur >= t:
best = min(best, j - i + 1); cur -= a[i]; i += 1Complexity
Time: O(n). Space: O(1).
Related problems
- Subarrays With Product Below K — Medium
- Subarray With Target Sum — Medium
- Container With Most Water — Medium
- Longest Substring Without Repeats — Medium
- Maximum Window Sum — Medium
- Sort Colors — Medium