Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 209. Minimum Size Subarray Sum

Find the length of the shortest contiguous subarray of positive integers whose sum is at least a given target (return 0 if none exists). This is a classic sliding-window / two-pointer problem exploiting positivity of nums to get an O(n) solution (follow-up asks for an O(n log n) alternative).

Asked at:

toast

DESCRIPTION

Input:

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

Output:

Explanation: The subarray [4, 3] has sum 7 and is the shortest subarray with sum >= 7

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
1 <= target <= 10^9
All integers in nums are positive

Understanding the Problem

Let's understand what we're being asked to do. We have an array of positive integers like [2, 3, 1, 2, 4, 3] and a target sum like 7. We need to find the shortest contiguous subarray whose sum is at least 7.

Tracing through: subarray [2,3,1,2] has sum 8 (length 4), subarray [3,1,2,4] has sum 10 (length 4), subarray [4,3] has sum 7 (length 2). The shortest is [4,3] with length 2!

Important constraint: All numbers are positive integers. This isn't just random data - the positivity property is crucial!

Edge cases to consider: What if no subarray sums to at least the target? (return 0). What if the entire array's sum is less than target? What if a single element is already >= target? What if the array is empty?

Brute Force Approach

The brute force approach checks every possible contiguous subarray. Use two nested loops: the outer loop picks the starting index, and the inner loop extends to each possible ending index, calculating the sum along the way. For each subarray whose sum is at least the target, track the minimum length found. This approach is straightforward but inefficient because it recalculates sums redundantly and doesn't exploit the positive integer property.

Visualization

def min_subarray_len(target, nums):
    """
    Find the minimal length of a contiguous subarray whose sum >= target.
    Brute force approach: check all possible subarrays.
    """
    n = len(nums)
    min_length = float('inf')
    
    # Outer loop: pick starting index
    for start in range(n):
        current_sum = 0
        
        # Inner loop: extend to each possible ending index
        for end in range(start, n):
            # Add current element to sum
            current_sum += nums[end]
            
            # Check if current subarray sum meets target
            if current_sum >= target:
                # Update minimum length found
                current_length = end - start + 1
                min_length = min(min_length, current_length)
    
    # Return 0 if no valid subarray found
    return 0 if min_length == float('inf') else min_length

Start brute force: check all subarrays

0 / 110

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We check all possible subarrays with nested loops, leading to quadratic time complexity. For each starting position, we potentially check all ending positions.

Space Complexity: O(1) We only use a few variables to track the current sum, minimum length, and loop indices, regardless of input size

Building Intuition

As we extend a subarray to the right by adding elements, the sum only increases (since all numbers are positive). As we shrink it from the left by removing elements, the sum only decreases.

This means once we find a valid subarray (sum >= target), we can try shrinking it from the left to find a shorter valid subarray, without needing to re-check all possibilities.

Because of the monotonic property (sum only grows when extending right, only shrinks when contracting left), we can use two pointers that each move in one direction only.

This transforms a problem that seems like it needs O(n²) time (checking all subarrays) into an O(n) solution where each element is visited at most twice (once by right pointer, once by left pointer).

Imagine you're measuring a rubber band stretched across an array. You extend the right end until the band covers enough elements to meet your target sum.

Once you've met the target, you try pulling in the left end to make the band shorter while still meeting the target. When it becomes too short (sum drops below target), you extend the right end again.

The key insight: because all numbers are positive, you never need to move a pointer backwards - each pointer only moves forward through the array once.

Common Mistakes

Forgetting to handle the case where no valid subarray exists - must return 0, not leave minLength uninitialized or return a large sentinel value

Moving the left pointer too aggressively - only shrink the window when the current sum is still >= target, not when it drops below

Not considering single-element subarrays - if one element is >= target, the answer is 1, not 0

Trying to apply this approach to arrays with negative numbers - the sliding window technique breaks down because removing elements from the left might increase the sum

Off-by-one errors in calculating subarray length - remember that length is right - left + 1, not right - left

Optimal Solution

The optimal approach uses a sliding window with two pointers. Start with both pointers at the beginning. Expand the window by moving the right pointer and adding elements to the sum. Once the sum meets or exceeds the target, try shrinking the window from the left while maintaining a valid sum, tracking the minimum length. Because all numbers are positive, each pointer only moves forward once through the array, achieving linear time complexity.

Visualization

def min_subarray_len(target, nums):
    """
    Find minimum length of contiguous subarray with sum >= target.
    Uses sliding window with two pointers for O(n) time complexity.
    """
    # Initialize variables
    n = len(nums)
    min_length = float('inf')
    window_sum = 0
    left = 0
    
    # Expand window with right pointer
    for right in range(n):
        # Add current element to window sum
        window_sum += nums[right]
        
        # Shrink window while sum is valid
        while window_sum >= target:
            # Update minimum length
            min_length = min(min_length, right - left + 1)
            
            # Remove leftmost element and shrink window
            window_sum -= nums[left]
            left += 1
    
    # Return result (0 if no valid subarray found)
    return min_length if min_length != float('inf') else 0

start

Start sliding window algorithm

0 / 23

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) Each element is visited at most twice (once when the right pointer passes it, once when the left pointer passes it), resulting in linear time complexity

Space Complexity: O(1) We only need two pointers (left and right), a running sum variable, and a minimum length tracker, all using constant space

What We've Learned

sliding-window mastery: Understanding when and why to use sliding-window data structure for this type of problem pattern
Algorithm optimization: Recognizing how to achieve O(n) time complexity through efficient problem decomposition
Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice

Test Your Understanding

Why is sliding-window the right data structure for this problem?

sliding-window provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid August, 2025

toast

Staff

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 209. Minimum Size Subarray Sum

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact