DSA problem
Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
This problem flips the usual sliding-window goal: instead of finding the longest valid window, we want the shortest window that satisfies a constraint. The brute-force approach of testing every subarray sum is O(n^2), and we want to do better by exploiting a structural property of the input.
The crucial property is that all elements are positive. This means the prefix sum is strictly increasing, so extending a window can only increase its sum and shrinking it can only decrease its sum. That monotonic behavior is exactly what makes a two-pointer window valid here.
The intuition for the sliding window is a grow-then-shrink rhythm. Expand the right pointer to accumulate elements until the running sum reaches target. The moment the window is valid, record its length, then aggressively shrink it from the left while it remains valid, looking for an even shorter qualifying window. Because each pointer only moves forward, the entire scan runs in O(n) time.
Examples
target = 7, nums = [2,3,1,2,4,3]2target = 4, nums = [1,4,4]1target = 11, nums = [1,1,1,1,1,1,1,1]0Constraints
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.