Minimum Size Subarray Sum

Sliding WindowTwo Pointers

20 min

Problem Statement

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

Example

Example 1:

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

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

Output: 2

The subarray [4,3] has the minimal length under the problem constraint.

Solution

This problem can be solved using a sliding window. We expand the window by moving the right pointer and adding the new element to the sum. When the sum is greater than or equal to the target, we shrink the window from the left and update the minimum length.

Algorithm Steps

Initialize `minLength` to infinity, `currentSum` to 0, and a left pointer `l` to 0.
Iterate through the array with a right pointer `r`, adding `nums[r]` to `currentSum`.
While `currentSum` is greater than or equal to the `target`:
Update `minLength` with the minimum of `minLength` and the current window size (`r - l + 1`).
Subtract `nums[l]` from `currentSum` and increment `l`.
If `minLength` is still infinity after the loop, return 0. Otherwise, return `minLength`.

Minimum Size Subarray Sum

Sliding Window Approach

Progress1 / 1

Ready to start the visualization

nums

Current Sum

Min Length

∞

Minimum Size Subarray Sum Solution


class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        l, total = 0, 0
        res = float("inf")

        for r in range(len(nums)):
            total += nums[r]
            while total >= target:
                res = min(r - l + 1, res)
                total -= nums[l]
                l += 1
        return 0 if res == float("inf") else res