Skip to main content
DSA patterns

Minimum Size Subarray Sum

mediumSliding window Must-do

Problem statement

You are given a positive integer target and a list nums of positive integers. Find the shortest block of neighbouring values in nums whose sum is at least target, and return the length of that block. If no block reaches target, return 0.

Examples

Example 1

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

Output: 2

Explanation: The block [4, 3] sums to 7 and has length 2. No single value reaches 7, so 2 is the shortest.

Example 2

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

Output: 0

Explanation: The whole list only sums to 8, which is less than 11, so no block works.

Hints

Hint 1: All numbers are positive, so making a block longer can only increase its sum. That is the fact the fast solutions rely on.

Approach

Optimal: Sliding window

Intuition

Think of a stretchy window over the list. Grow it on the right until its sum reaches target. Now it is a valid block, so write down its length, then shrink it from the left to see if a shorter block still works. Shrinking is safe only because the numbers are positive: removing a value always lowers the sum, so once the sum drops below target, no shorter window ending at this right can work and we move on. This is faster than the prefix approach because it needs no extra array and no binary search.

Steps

  1. Set left = 0, total = 0, best = 0.
  2. For each right, add nums[right] to total.
  3. While total >= target: record right - left + 1 if it is the best so far, subtract nums[left] from total, and move left one step right.
  4. Return best.

Dry run

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

right added total after adding shrinking best
0 2 2 none 0
1 3 5 none 0
2 1 6 none 0
3 2 8 length 4, drop 2 → total 6 4
4 4 10 length 4, drop 3 → 7; length 3, drop 1 → 6 3
5 3 9 length 3, drop 2 → 7; length 2, drop 4 → 3 2

Edge cases: if the sum never reaches target, the while never runs and best stays 0. A single value that is already at least target gives length 1.

Complexity

Time O(n) - The `right` pointer moves forward n times in total. The `left` pointer only moves forward and never passes `right`, so it also moves at most n times. The inner `while` loop looks nested, but across the whole run it adds at most n steps.

Space O(1) - We keep the window sum, two pointers and the best length. The window is never stored as a separate list. Memory does not grow with the input.

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


if __name__ == "__main__":
    print(Solution().minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))
    print(Solution().minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: shortest contiguous piece whose sum is at least a target, all numbers positive
  • Idea: sliding window; grow the right end, and while the sum is at least the target, record the length and shrink from the left
  • Cost: O(n) time, O(1) space
  • Trap: return 0 when no window works; shrinking only works because the numbers are positive

Interview follow-ups

  • Return the start and end positions of the shortest block.

    Store two more numbers, best_left and best_right. Each time the window sum reaches target and the window is shorter than best, copy the current left and right into them before you shrink the window. At the end, return the pair, or an empty result if no block reached target. Time stays O(n) and space stays O(1).

  • Handle lists that may contain negative numbers.

    The sliding window breaks, because removing a value from the left can now increase the sum. Switch to prefix sums with a monotonic deque of positions. For each position j, while the front position i gives prefix[j] - prefix[i] >= target, record j - i and pop the front. Before pushing j, pop from the back while the back prefix is greater than or equal to prefix[j], since j is a later and no worse start. This runs in O(n) time with O(n) space.

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 O(n) per value. Counting the total moves of both pointers, not the loop nesting, is the right way to measure it.

No. With negatives, dropping a value from the left can increase the sum, so the shrink step can miss answers. The prefix array is also no longer sorted, so the binary search breaks. That version needs a monotonic deque over the prefix sums, shown in the follow-ups.

The problem defines 0 as the "no block" answer, since a real block always has length at least 1. In the code, best == 0 also means "nothing found yet", which is why the update checks best == 0 or length < best.

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 never negative, which is exactly the condition the window needs.