DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Minimum Size Subarray Sum

mediumSliding window Must-do

Problem statement

You are given a positive integer target and an array nums of positive integers. Find the shortest contiguous block of nums whose sum is at least target, and return its length. If no block reaches target, return 0.

Examples

Example 1

Input: target = 11, nums = [3, 1, 4, 6, 2, 5]

Output: 3

Explanation: [4, 6, 2] sums to 12. No block of two neighbours reaches 11 (the largest pair is 4 + 6 = 10).

Example 2

Input: target = 50, nums = [5, 10, 15]

Output: 0

Explanation: Even the whole array only sums to 30.

Hints

Approach

Use a variable-size sliding window. Extend the right edge one element at a time. Whenever the window sum reaches target, record its length, then drop elements from the left while the sum still reaches target, recording each shorter length.

  1. left = 0, total = 0, best = 0.
  2. For each right: add nums[right] to total.
  3. While total >= target: update best with right - left + 1, subtract nums[left], move left forward.
  4. Return best.

Shrinking is safe only because the numbers are positive: removing an element always lowers the sum, so once the sum falls below target, no smaller window ending at right can work.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def minSubArrayLen(self, target: int, nums: list[int]) -> int:
left = 0
total = 0
best = 0
for right, x in enumerate(nums):
total += x
while total >= target:
length = right - left + 1
if best == 0 or length < best:
best = length
total -= nums[left] # try a shorter window
left += 1
return best

Follow-up questions

  • Return the start and end indices of the shortest block.
  • Handle arrays that may contain negative numbers.

Frequently asked questions

The left pointer only moves forward and never passes right. Across the whole run it moves at most n times in total, so the inner loop adds O(n) work overall, not per element.

No. With negatives, dropping an element can increase the sum, so the shrink step can miss answers and the prefix array is no longer sorted. That version needs a monotonic deque over prefix sums.

It answers questions like "what is the shortest stretch of consecutive minutes in which errors reached a threshold?" or "the fewest consecutive log batches that add up to 1 GB". Counts and sizes are non-negative, which is exactly the condition the window needs.