Coding interview problems › Sliding Window

🪟 Sliding Window Medium

Minimum Size Subarray Sum

Minimum Size Subarray Sum explained: a variable sliding window grows until the sum reaches the target, then shrinks from the left in O(n). Tested Python.

Also searched as: smallest subarray with sum at least target · variable size sliding window

🪟

Try it live Free

Sliding Window

Watch the window add what enters and subtract what leaves. In this problem the window size changes: it stretches right until the sum is enough, then shrinks from the left.

Open the playground →

The problem

Given a list of positive integers and a positive target, return the length of the shortest contiguous subarray whose sum is at least target, or 0 if none exists.

Inputtarget = 7, nums = [2, 3, 1, 2, 4, 3]
Output2

[4, 3].

Inputtarget = 11, nums = [1, 1, 1, 1]
Output0

The key insight

Since every number is positive, growing the window always increases its sum and shrinking always decreases it. So extend the right edge until the sum is big enough, then pull the left edge in as far as possible while the sum stays big enough, recording the length each time.

Brute force first: Trying every start and extending until the sum is reached is O(n²).

Step-by-step approach

  1. Set left = 0, s = 0, best = infinity.
  2. For each right, add nums[right] to s.
  3. While s >= target: record right - left + 1, subtract nums[left], move left right.
  4. Return best, or 0 if it was never set.

Python solution

PYTHON 3tested
def min_subarray_len(target, nums):
    left = s = 0
    best = float("inf")
    for right, x in enumerate(nums):
        s += x
        while s >= target:             # shrink while still valid
            best = min(best, right - left + 1)
            s -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

Complexity

TimeO(n)
SpaceO(1)

Each index enters the window once and leaves at most once, so the nested while loop does O(n) total work.

Common mistakes

Frequently asked questions

What is the time and space complexity of Minimum Size Subarray Sum?

O(n) time and O(1) space with the variable sliding window. A prefix sums plus binary search approach is O(n log n).

Why must the numbers be positive?

Positivity guarantees that a longer window has a larger sum, so once a window is valid there is no point extending it further from the same left edge. With negatives that guarantee breaks.

Is the nested loop really O(n)?

Yes. left only moves forward and never passes right, so across the whole run the inner loop executes at most n times.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Sliding Window Sliding Window lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.