How do you approach Minimum Size Subarray Sum?

All numbers are positive, so growing a window only increases its sum and shrinking only decreases it.

What is the time complexity of Minimum Size Subarray Sum?

Time complexity: O(n) - left and right each advance at most n times. Space complexity: O(1).

What are common mistakes on Minimum Size Subarray Sum?

Shrinking with if instead of while - one removal is often not enough to restore the invariant. Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove. Never recording the answer for a window that ends at the last index.

gitGood.dev

← Back to problems

Minimum Size Subarray Sum

MediumAlgorithms

Description

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.

Example 1

Input: target = 7, nums = [2,3,1,2,4,3]

Output: 2

Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2

Input: target = 4, nums = [1,4,4]

Output: 1

Example 3

Input: target = 11, nums = [1,1,1,1,1,1,1,1]

Output: 0

Explanation: The whole array sums to 8 < 11, so no valid subarray exists.

Constraints

- 1 <= target <= 10^9 - 1 <= nums.length <= 10^5 - 1 <= nums[i] <= 10^4

Minimum Size Subarray Sum: approach, complexity and pitfalls

A medium sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

If you are stuck

Show the 3-step hint ladder

All numbers are positive, so growing a window only increases its sum and shrinking only decreases it.
Expand the window to the right until the sum reaches the target.
Then shrink from the left as much as possible while the sum stays >= target, recording the window length each time.

The optimal approach

Show the approach: Shrinkable Sliding Window

Because every element is positive, the window sum is monotonic in the window size, which makes a two-pointer window valid. Expand `right` and add to the running sum. Whenever the sum is at least `target`, record the window length and shrink from `left` - keep shrinking while the sum still meets the target, since a shorter qualifying window is always better.

Time: O(n) - left and right each advance at most n times
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.