MediumArrayBinary SearchSliding WindowPrefix SumUpdated Sep 2026

209. Minimum Size Subarray Sum

Asked at Meta

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You get an array of positive integers nums and a positive integer target. Find the length of the shortest contiguous subarray whose sum is at least target. A subarray means a block of neighbouring elements — you cannot skip elements.

If no subarray reaches the target, return 0. Because every number is positive, adding more elements only makes the sum bigger, which is the key fact that makes a fast solution possible.

Find the shortest block that reaches the target

numssum = 7, length 2231243012345The block [4,3] sums to 7, so the answer is 2.
We need the fewest neighbouring elements whose sum is at least 7.

Constraints

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

Examples

Example 1
Inputtarget = 7, nums = [2,3,1,2,4,3]
Output2
WhyThe block [4,3] sums to 7, which meets the target, and it uses only 2 elements. No single element is >= 7, so 2 is the smallest possible length.
Example 2
Inputtarget = 4, nums = [1,4,4]
Output1
WhyThe element 4 alone equals the target, so a subarray of length 1 is enough.
Example 3
Inputtarget = 11, nums = [1,1,1,1,1,1,1,1]
Output0
WhyThe whole array sums to 8, which is still less than 11, so no valid subarray exists.

Asked At

1 companies
CompanyDifficulty
MetaMediumView all Meta questions →

How to Think About It

1

Brute force: check every subarray with two nested loops — O(n^2).

2

Prefix sum + binary search: for each start index, binary search for the smallest end where prefix[end] - prefix[start] >= target.

3

Sliding window: expand right to accumulate sum, shrink left to find minimum length.

4

The sliding window approach is optimal at O(n) since all values are positive.

5

Maintain a running sum and update the answer each time the window sum meets or exceeds the target.

Optimal Approach

Use a sliding window. Expand the right pointer to accumulate the sum. Whenever the sum >= target, record the length and shrink the left pointer to try to minimize. Continue until the right pointer reaches the end. Return the minimum length found, or 0 if none was found. This runs in O(n) time with O(1) space since all values are positive.

Sliding window: grow right, shrink left

numssum = 8231243012345leftrightStep 1 — right reaches index 3, sum is 8, which isalready >= 7numssum = 6 < 7231243012345leftrightStep 2 — drop 2 from the left, but now the sum fallsbelow 7, so we must grow againnumssum = 7, length 2231243012345leftrightStep 3 — right adds 4 and 3; the window [4,3] sums to7 and is the shortest foundwhile sum >= target: best = min(best, right - left + 1) sum -= nums[left]; left += 1
Right adds elements until the sum is big enough, then left removes elements to make the window as short as possible.
ComplexityTime O(n)Space O(1)Each element enters and leaves the window at most once, and we only keep a few counters.

What Trips People Up in Real Interviews

1

Clarify that all numbers are positive — this is critical for the sliding window to work.

2

Edge case: return 0 if no valid subarray exists (total sum < target).

3

Edge case: single element equal to or greater than target returns length 1.

4

Mention the O(n log n) prefix sum + binary search approach as an alternative.

5

Trace through [2,3,1,2,4,3] with target=7 to show the sliding window shrinking.

Solution Code

O(n) time
def minSubArrayLen(target: int, nums: list[int]) -> int:
    left = 0
    total = 0
    min_len = float('inf')
    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            min_len = min(min_len, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if min_len == float('inf') else min_len

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Size Subarray Sum problem?

Given an array of positive integers and a positive integer target, find the minimal length of a subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

How do you solve Minimum Size Subarray Sum?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Size Subarray Sum?

Minimum Size Subarray Sum is asked at Meta. It is a medium difficulty problem.

What are common mistakes on Minimum Size Subarray Sum?
  • Clarify that all numbers are positive — this is critical for the sliding window to work.
  • Edge case: return 0 if no valid subarray exists (total sum < target).
  • Edge case: single element equal to or greater than target returns length 1.
  • Mention the O(n log n) prefix sum + binary search approach as an alternative.
  • Trace through [2,3,1,2,4,3] with target=7 to show the sliding window shrinking.