MediumArraysSliding WindowBinary Search

Minimum Size Subarray Sum

2 approaches, code in every language

You are handed an array of positive integers together with a target value. Your job is to find the length of the shortest contiguous stretch of elements whose sum is at least as large as the target. When no stretch of the array can reach the target, report 0 instead.

Because every element is strictly positive, extending a window to the right can only increase its sum and dropping an element from the left can only decrease it. That monotonic behaviour is exactly what lets a single sweep find the shortest qualifying window.

Example 1

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

Output: 2

The two elements 4 and 3 sit next to each other and add up to 7, and no shorter run of elements manages to reach 7.

Example 2

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

Output: 1

A single card holding 4 already meets the target on its own, so the minimal length is 1.

Constraints

1 ≤ target ≤ 10^9
1 ≤ nums.length ≤ 10^5
1 ≤ nums[i] ≤ 10^4

Grow and shrink a window

Expand a window to the right to accumulate sum, and whenever the sum clears the target, shrink from the left while recording the smallest valid width.

Loading animation…

Intuition

Since all values are positive, once a window meets the target there is no reason to keep extra elements on the left, they only make the window longer. So push the right edge forward to build up the sum, and the moment the sum is large enough, pull the left edge in as far as possible while the target is still satisfied. Each element enters and leaves the window at most once, giving a linear scan.

Algorithm walkthrough

1Keep a left pointer, a running sum, and a best-length tracker set to a value larger than any real window.
2Move the right pointer across the array, adding each visited value to the running sum.
3While the running sum is at least the target, update the best length with the current window width, then subtract the left element and advance the left pointer.
4Continue until the right pointer reaches the end of the array.
5If the best length was never improved, return 0; otherwise return the best length found.

Implementation

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        total = 0
        best = len(nums) + 1
        for right in range(len(nums)):
            total += nums[right]
            while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1
        return 0 if best == len(nums) + 1 else best

Time

O(n)

Space

O(1)

Each index is added and removed from the window at most once, so the total work is linear.

Prefix sums with binary search

Build cumulative sums, then for every start index binary-search the earliest end index whose cumulative sum clears the required threshold.

Loading animation…

Intuition

The cumulative sum array is strictly increasing because all values are positive. For a fixed start, the shortest valid window ends at the first position where the cumulative sum reaches the start's prefix plus the target. Since the prefix array is sorted, that first position can be located with binary search, trading the pure linear scan for an O(n log n) method that is handy when you already need prefix sums for other queries.

Algorithm walkthrough

1Construct a prefix array where prefix[i] holds the sum of the first i elements.
2For each start index i, compute the threshold prefix[i] + target that the window's end must reach.
3Binary-search the prefix array (over indices greater than i) for the first entry that is at least the threshold.
4If such an index exists, its distance from i is a candidate window length; keep the smallest candidate seen.
5Return 0 if no candidate was ever found, otherwise the smallest length.

Implementation

import bisect

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        best = n + 1
        for i in range(n):
            need = prefix[i] + target
            j = bisect.bisect_left(prefix, need, i + 1)
            if j <= n:
                best = min(best, j - i)
        return 0 if best == n + 1 else best

Time

O(n log n)

Space

O(n)

Building the prefix array is linear; each of the n binary searches costs log n.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Fewest Shifts to Clear the Quota is our own problem on the technique behind Minimum Size Subarray Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free