CoreCoding

Built for depth, not noise.

Back to DSA track

Minimum Size Subarray Sum

Find the smallest contiguous subarray whose sum is at least the target.

MEDIUM

Problem intuition

The brute-force version starts a new sum from every index and checks all possible endings.
The sliding-window solution takes advantage of positive numbers: once the sum is large enough, shrinking from the left is the only way to improve the answer.

Solution

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Try every start and end

Accumulate sums from each start index until you cross the target.
This is correct, but it is still quadratic in the worst case.
▸
Time complexity: O(n^2)
- each start index may scan far to the right before deciding whether the target is reached.
▸
Space complexity: O(1)
- the algorithm only maintains the current sum and the best length found.

Solution 2

Sliding window on positive numbers

Expand right until the running sum reaches the target.
Then shrink left as much as possible while the window stays valid.
▸
Time complexity: O(n)
- both the left and right pointers move forward through the array only once.
▸
Space complexity: O(1)
- only the running sum, two pointers, and the best answer are tracked.