Minimum size subarray sum: definition
A subarray is a contiguous part of an array. Find the shortest one whose sum is at least target. This problem uses a variable-size sliding window over positive integers.
Task example: Minimum Size Subarray Sum
Given positive integers nums and a positive target, return the minimum length of a contiguous subarray with sum >= target. Return 0 if no such subarray exists. Keep the original order.
For target = 7, [4, 3] has length 2. No single value reaches 7, so 2 is minimal. The sum may exceed the target; it does not have to equal it.
Brute force: video explanation
target = 7, nums = [2, 3, 1, 2, 4, 3] → 2
Prefer reading? Follow the steps below.
- Choose left, reset total to 0, then advance right and add each value. Use best = len(nums) + 1 to mean no answer yet.
- Once total >= target, record right - left + 1 and stop this start. A longer subarray with the same start cannot be a shorter answer.
- Try every remaining start. The best length improves from 4 to 3 to 2. Return 0 only if best still equals its initial marker.
Time complexity · O(n²)
There are n possible starts and up to n additions per start. If the target is unreachable, all suffixes are scanned: O(n²) time.
Space complexity · O(1)
Only indices, a running sum, and the best length are stored. No subarrays are copied, so extra space is O(1).
Sliding window: video explanation
target = 7, nums = [2, 3, 1, 2, 4, 3] → 2
Prefer reading? Follow the steps below.
- Add nums[right] to total. While total >= target, record the current length before subtracting nums[left] and advancing left.
- Keep shrinking while the window is valid. At right = 4, sums 10 and 7 give lengths 4 and 3. At right = 5, sums 9 and 7 give lengths 3 and 2.
- When total falls below target, grow right again. Finish the scan and return best, or 0 if no valid window was found.
Why it works: positive values make the sum increase when the window grows and decrease when it shrinks. Removing a valid start is safe: extending it later cannot produce a shorter answer. Reusing total avoids repeated scans. This method does not apply to arbitrary negative values.
Time complexity · O(n)
Each value is added once and removed at most once. Both pointers move only forward, so the total work is O(n), even with a nested while loop.
Space complexity · O(1)
Only indices, a running sum, and the best length are stored. No subarrays are copied, so extra space is O(1).