We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Size Subarray Sum

Difficulty: Medium

Problem Description

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

Key Insights

  • A subarray is defined as a contiguous part of the array.
  • We need to find the shortest subarray such that its sum is at least target.
  • A sliding window approach can efficiently find the required subarray by maintaining a dynamic range of sums.
  • If the sum of the current subarray meets or exceeds the target, we can attempt to shrink the window from the left to minimize the length.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We can use a sliding window (or two-pointer) technique to solve this problem. The idea is to expand the window by moving the right pointer to include more elements and calculate the sum. Once the sum meets or exceeds the target, we will check if we can shrink the window from the left by moving the left pointer, while keeping track of the minimum length of the valid subarray found.

Code Solutions

def minSubArrayLen(target, nums):
    left = 0
    total = 0
    min_length = float('inf')

    for right in range(len(nums)):
        total += nums[right]

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

    return min_length if min_length != float('inf') else 0
← Back to All Questions