Minimum size subarray sum

Medium

📘 Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [nums[l], nums[l+1], ..., nums[r-1], nums[r]] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

---

🔍 Example

Input :

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

Output: : 2

subarray [4,2] has the minimum sum >= target

---

Intuition

This is a classic sliding window problem because:

• All numbers are positive, so increasing the window always increases the sum.

• When the current sum is ≥ target, we try to shrink the window from the left to find the smallest valid window.

🛠️ Solution

🧮 Step-by-step Algorithm

• Initialize two pointers: left = 0, right as the loop index.

• Expand the window by adding 1nums[right]1 to the curr_sum.

• Once curr_sum ≥ target, try to shrink the window from the left while the condition still holds.

Track the minimum length of such a window.

🧑‍💻 Code

def minSubArrayLen(target: int, nums: list[int]) -> int:
    n = len(nums)
    left = 0
    curr_sum = 0
    min_len = float('inf')

    for right in range(n):
        curr_sum += nums[right]

        while curr_sum >= target:
            min_len = min(min_len, right - left + 1)
            curr_sum -= nums[left]
            left += 1

    return 0 if min_len == float('inf') else min_len

🕒 Time Complexity: \(O(n)\) - Each index is visited at most twice (once by right, once by left)

📦 Space Complexity: \(O(1)\) — no extra space used