LeetCode 209: Minimum Size Subarray Sum Solution in Python Explained

Problem Statement

In LeetCode 209: Minimum Size Subarray Sum, you’re given:

• target: An integer representing the minimum sum to achieve.
• nums: An array of positive integers.
• Your task is to return the length of the shortest contiguous subarray with a sum ≥ target, or 0 if no such subarray exists.

This is a sliding window or prefix sum problem, distinct from Trie implementation in LeetCode 208: Implement Trie (Prefix Tree), focusing instead on array subsegments.

Constraints

• 1 ≤ target ≤ 10⁹.
• 1 ≤ nums.length ≤ 10⁵.
• 1 ≤ nums[i] ≤ 10⁴.

Examples

Let’s see some cases:

Copy codeInput: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: Subarray [4,3] has sum 7 with length 2, the smallest possible.

Copy codeInput: target = 4, nums = [1,4,4]
Output: 1
Explanation: Subarray [4] has sum 4 with length 1.

Copy codeInput: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Explanation: No subarray sums to 11.

These examples show we’re finding the minimal length meeting the target.

Understanding the Problem

How do we solve LeetCode 209: Minimum Size Subarray Sum in Python? For target = 7, nums = [2,3,1,2,4,3], we need a subarray summing to at least 7 with the smallest length—[4,3] works (length 2). A brute-force approach might check all subarrays (O(n²)), but that’s too slow. This isn’t a graph problem like LeetCode 207: Course Schedule; it’s about optimizing array traversal. We’ll use: 1. Sliding Window: O(n) time, O(1) space—our best solution. 2. Prefix Sum with Binary Search: O(n log n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Sliding Window Approach

Explanation

The Sliding Window approach uses two pointers to maintain a dynamic window:

• left: Start of the window.
• right: End of the window.
• window_sum: Sum of elements in the window.
• Expand right to increase the sum; shrink left when sum ≥ target to minimize length.
• Track the smallest valid length.

Since nums contains positive integers, the sum increases as the window grows and decreases as it shrinks, making this O(n) time and O(1) space—our best solution.

For [2,3,1,2,4,3], target = 7, it finds [4,3] efficiently.

Step-by-Step Example

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

Goal: Return 2.

• Step 1: Initialize.
• left = 0, window_sum = 0, min_length = float('inf').
• Step 2: Iterate with right.
• right = 0: window_sum = 2, < 7, continue.
• right = 1: window_sum = 5, < 7, continue.
• right = 2: window_sum = 6, < 7, continue.
• right = 3: window_sum = 8, ≥ 7:
• min_length = 4 (0 to 3).
• Shrink: window_sum -= 2, left = 1, window_sum = 6, < 7.
• right = 4: window_sum = 10, ≥ 7:
• min_length = 4 (1 to 4).
• Shrink: window_sum -= 3, left = 2, window_sum = 7, ≥ 7.
• min_length = 3 (2 to 4).
• Shrink: window_sum -= 1, left = 3, window_sum = 6, < 7.
• right = 5: window_sum = 9, ≥ 7:
• min_length = 3 (3 to 5).
• Shrink: window_sum -= 2, left = 4, window_sum = 7, ≥ 7.
• min_length = 2 (4 to 5).
• Shrink: window_sum -= 4, left = 5, window_sum = 3, < 7.
• Step 3: Finish.
• min_length = 2, return 2.

Example 2: target = 4, nums = [1,4,4]

Goal: Return 1.

• Step 1: left = 0, window_sum = 0, min_length = float('inf').
• Step 2:
• right = 0: window_sum = 1, < 4.
• right = 1: window_sum = 5, ≥ 4:
• min_length = 2.
• Shrink: window_sum -= 1, left = 1, window_sum = 4, ≥ 4.
• min_length = 1.
• Shrink: window_sum -= 4, left = 2, window_sum = 0.
• right = 2: window_sum = 4, ≥ 4:
• min_length = 1.
• Output: 1.

How the Code Works (Sliding Window) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef minSubArrayLen(target: int, nums: list[int]) -> int:
    # Line 1: Initialize variables
    left = 0
    # Left pointer (e.g., 0)
    window_sum = 0
    # Current window sum (e.g., 0)
    min_length = float('inf')
    # Smallest valid length (e.g., infinity)

    # Line 2: Iterate with right pointer
    for right in range(len(nums)):
        # Expand window (e.g., right = 0)
        window_sum += nums[right]
        # Add current element (e.g., window_sum = 2)

        # Line 3: Shrink window if sum ≥ target
        while window_sum >= target:
            # Check if window is valid (e.g., 8 >= 7)
            min_length = min(min_length, right - left + 1)
            # Update min length (e.g., min(inf, 4) = 4)
            window_sum -= nums[left]
            # Subtract left element (e.g., 8 - 2 = 6)
            left += 1
            # Move left pointer (e.g., left = 1)

    # Line 4: Return result
    return min_length if min_length != float('inf') else 0
    # Return smallest length or 0 (e.g., 2)

This solution is optimal and intuitive.

Alternative: Prefix Sum with Binary Search Approach

Explanation

The Prefix Sum with Binary Search approach uses cumulative sums:

• Compute prefix sums (prefix[i] = sum of nums[0:i]).
• For each end index, binary search for the start where prefix[end] - prefix[start-1] ≥ target.
• Track the smallest length.

It’s O(n log n) time (n binary searches) and O(n) space (prefix array), offering a different perspective.

Step-by-Step Example

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

• Prefix: [0, 2, 5, 6, 8, 12, 15].
• end = 0: 2 < 7, skip.
• end = 1: 5 < 7, skip.
• end = 3: 8 ≥ 7, search 8 - x ≥ 7, x ≤ 1, length = 4.
• end = 4: 12 ≥ 7, 12 - 5 = 7, length = 3.
• end = 5: 15 - 8 = 7, length = 2.
• Output: 2.

How the Code Works (Prefix Sum)

Copy codefrom bisect import bisect_right

def minSubArrayLenPrefix(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]

    min_length = float('inf')
    for end in range(n):
        need = prefix[end + 1] - target
        start = bisect_right(prefix, need)
        if start <= end + 1 and prefix[end + 1] - prefix[start - 1] >= target:
            min_length = min(min_length, end - start + 2)

    return min_length if min_length != float('inf') else 0

Complexity

• Sliding Window:
• Time: O(n) – single pass with amortized shrinking.
• Space: O(1) – just pointers.
• Prefix Sum with Binary Search:
• Time: O(n log n) – binary search per index.
• Space: O(n) – prefix array.

Efficiency Notes

Sliding Window is our best solution with O(n) time and O(1) space, perfect for this problem. Prefix Sum with Binary Search is slower but showcases an alternative technique.

Key Insights

• Window: Dynamic size adjustment.
• Positive Numbers: Enables sliding.
• Minimal Length: Key focus.

Additional Example

For target = 15, nums = [5,1,3,5,10,7,4]:

• Sliding: [10,7], length = 2.
• Prefix: Same result.

Edge Cases

• target > sum(nums): 0.
• Single element ≥ target: 1.
• All small: 0.

Both handle these well.

Final Thoughts

LeetCode 209: Minimum Size Subarray Sum in Python is a classic sliding window challenge. Sliding Window excels in speed and simplicity, while Prefix Sum with Binary Search offers a unique angle. Want more? Try LeetCode 3: Longest Substring Without Repeating Characters or LeetCode 76: Minimum Window Substring. Test your skills—Solve LeetCode 209 on LeetCode with target = 7, nums = [2,3,1,2,4,3] (expecting 2)—find that subarray today!