LeetCode 209 - Minimum Size Subarray Sum

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem gives us an array of positive integers called nums and a positive integer called target. We need to find the smallest possible length of a contiguous subarray whose sum is greater than or equal to target.

A contiguous subarray means the elements must appear next to each other in the original array. We are not allowed to skip elements.

For example, if:

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

then the subarray [4,3] has a sum of 7, and its length is 2. No subarray of length 1 satisfies the condition, so the correct answer is 2.

The important detail is that we are minimizing the length, not the sum itself.

The constraints are large:

nums.length can be up to 10^5
each value in nums is positive
target can be as large as 10^9

These constraints immediately tell us that an O(n^2) brute-force solution may be too slow in the worst case. With 100,000 elements, checking every possible subarray would result in billions of operations.

The fact that all numbers are positive is the key property that enables an efficient solution. Since every element is greater than zero, expanding a window always increases the sum, and shrinking a window always decreases the sum. This monotonic behavior makes the sliding window technique possible.

Several edge cases are important to identify early:

No valid subarray exists, in which case we must return 0
A single element may already satisfy the target
The entire array may be required to reach the target
The array may contain many small values that never reach the target
Since values are positive, we never need to worry about negative numbers breaking the sliding window logic

Approaches

Brute-Force Approach

The most straightforward solution is to examine every possible contiguous subarray.

We can choose every starting index i, then extend the subarray one element at a time toward the right while maintaining the running sum. Whenever the sum becomes greater than or equal to target, we compute the subarray length and update the minimum answer.

This approach is correct because it explicitly checks all possible subarrays, guaranteeing that the shortest valid one will eventually be found.

However, the time complexity is too high. There are O(n^2) possible subarrays in an array of size n, and in the worst case we may examine most of them. With n = 10^5, this becomes computationally infeasible.

Optimal Sliding Window Approach

The key observation is that all numbers are positive.

Because of this:

Expanding the window to the right can only increase the sum
Shrinking the window from the left can only decrease the sum

This allows us to maintain a dynamic window using two pointers.

We expand the right pointer until the window sum becomes large enough. Once the sum reaches or exceeds target, we try to shrink the window from the left as much as possible while still maintaining the condition. This guarantees that for every right boundary, we find the smallest valid window ending at that position.

Instead of recomputing sums repeatedly, we maintain a running sum that updates incrementally as pointers move.

Since each element is added to the window once and removed once, the algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray
Optimal Sliding Window	O(n)	O(1)	Uses two pointers and a running sum

Algorithm Walkthrough

Initialize two pointers called left and right.

The left pointer represents the beginning of the current window, and the right pointer represents the end. 2. Maintain a running variable called current_sum.

This variable stores the sum of all elements currently inside the window. Instead of recomputing the sum every time, we update it incrementally as the window changes. 3. Initialize the answer variable.

We store the minimum valid length found so far. A common approach is to initialize it to infinity so that any valid subarray length will replace it. 4. Expand the window by moving right.

For each position of right, add nums[right] to current_sum. 5. Check whether the current window satisfies the condition.

If current_sum >= target, then the current window is valid. 6. Shrink the window from the left while it remains valid.

Since we want the minimum length, we should try to make the window as small as possible.

While current_sum >= target:

Update the minimum length
Remove nums[left] from current_sum
Increment left

Continue until the entire array has been processed.

Every possible minimal valid window will be considered exactly once. 8. Return the result.

If no valid subarray was found, return 0. Otherwise, return the minimum length recorded.

Why it works

The algorithm works because all numbers are positive. Once a window reaches the target sum, any larger window extending further right cannot produce a shorter answer unless we first shrink from the left.

The sliding window always maintains a contiguous subarray, and the inner shrinking loop guarantees that whenever a valid window exists for a given right boundary, we reduce it to the smallest possible valid window. Therefore, every candidate minimum is examined, and the global minimum is correctly found.

Python Solution

from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        current_sum = 0
        min_length = float('inf')

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

            while current_sum >= target:
                window_length = right - left + 1
                min_length = min(min_length, window_length)

                current_sum -= nums[left]
                left += 1

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

The implementation begins by initializing the sliding window state. The left pointer starts at index 0, and current_sum tracks the sum of elements inside the current window.

The outer loop expands the window by moving the right pointer across the array. Each new element is added to current_sum.

Whenever the running sum becomes greater than or equal to target, the inner while loop begins shrinking the window from the left side. This step is critical because it ensures we minimize the current valid window before moving on.

The expression:

right - left + 1

computes the current window length.

After recording the length, the algorithm removes the leftmost element from the running sum and advances the left pointer. This continues until the window is no longer valid.

At the end, if min_length was never updated, no valid subarray exists, so the function returns 0.

Go Solution

func minSubArrayLen(target int, nums []int) int {
	left := 0
	currentSum := 0
	minLength := len(nums) + 1

	for right := 0; right < len(nums); right++ {
		currentSum += nums[right]

		for currentSum >= target {
			windowLength := right - left + 1

			if windowLength < minLength {
				minLength = windowLength
			}

			currentSum -= nums[left]
			left++
		}
	}

	if minLength == len(nums)+1 {
		return 0
	}

	return minLength
}

The Go implementation follows the same sliding window logic as the Python version.

One notable difference is that Go does not have a built-in infinity value for integers in the same convenient way Python does. Instead, the implementation initializes minLength to len(nums) + 1, which is guaranteed to be larger than any valid subarray length.

Go slices are dynamically sized views over arrays, so iterating through nums works efficiently without additional memory allocation.

Since the problem constraints fit comfortably within Go's integer range, integer overflow is not a concern here.

Worked Examples

Example 1

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

Step	right	nums[right]	current_sum	left	Action	min_length
Start	-	-	0	0	Initialize	inf
1	0	2	2	0	Expand window	inf
2	1	3	5	0	Expand window	inf
3	2	1	6	0	Expand window	inf
4	3	2	8	0	Valid window found	4
5	3	-	6	1	Shrink window	4
6	4	4	10	1	Valid window found	4
7	4	-	7	2	Shrink window	3
8	4	-	6	3	Shrink window	2
9	5	3	9	3	Valid window found	2
10	5	-	7	4	Shrink window	2
11	5	-	3	5	Shrink window	2

Final answer:

The smallest valid subarray is [4,3].

Example 2

target = 4
nums = [1,4,4]

Step	right	nums[right]	current_sum	left	Action	min_length
1	0	1	1	0	Expand window	inf
2	1	4	5	0	Valid window	2
3	1	-	4	1	Shrink window	1
4	1	-	0	2	Shrink window	1
5	2	4	4	2	Valid window	1

Final answer:

A single element already satisfies the target.

Example 3

target = 11
nums = [1,1,1,1,1,1,1,1]

The total sum of the entire array is only 8, which is less than 11.

The sliding window never reaches the target, so min_length is never updated.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the window at most once
Space	O(1)	Only a few variables are used regardless of input size

The linear time complexity comes from the fact that both pointers only move forward. Although there is a nested while loop, the total number of left pointer movements across the entire algorithm is at most n. Therefore, the total work remains proportional to the size of the array.

The algorithm uses constant extra memory because it only stores a few integer variables and does not allocate additional data structures.

Test Cases

from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        current_sum = 0
        min_length = float('inf')

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

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

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

sol = Solution()

assert sol.minSubArrayLen(7, [2,3,1,2,4,3]) == 2  # standard example
assert sol.minSubArrayLen(4, [1,4,4]) == 1  # single element satisfies target
assert sol.minSubArrayLen(11, [1,1,1,1,1,1,1,1]) == 0  # no valid subarray
assert sol.minSubArrayLen(5, [5]) == 1  # single-element array valid
assert sol.minSubArrayLen(6, [5]) == 0  # single-element array invalid
assert sol.minSubArrayLen(15, [1,2,3,4,5]) == 5  # entire array required
assert sol.minSubArrayLen(100, [1,2,3,4,5]) == 0  # impossible target
assert sol.minSubArrayLen(3, [1,1,1,1,1]) == 3  # multiple equal values
assert sol.minSubArrayLen(8, [2,2,2,2]) == 4  # exact full-array match
assert sol.minSubArrayLen(7, [8]) == 1  # value larger than target
assert sol.minSubArrayLen(10, [1,2,3,4]) == 4  # exact total sum

Test	Why
`target=7, nums=[2,3,1,2,4,3]`	Standard sliding window example
`target=4, nums=[1,4,4]`	Single-element solution exists
`target=11, nums=[1,1,1,1,1,1,1,1]`	No valid subarray exists
`target=5, nums=[5]`	Single-element array exactly matches
`target=6, nums=[5]`	Single-element array fails
`target=15, nums=[1,2,3,4,5]`	Entire array needed
`target=100, nums=[1,2,3,4,5]`	Impossible target
`target=3, nums=[1,1,1,1,1]`	Repeated small values
`target=8, nums=[2,2,2,2]`	Full-array exact match
`target=7, nums=[8]`	Single value exceeds target
`target=10, nums=[1,2,3,4]`	Total sum exactly equals target

Edge Cases

One important edge case occurs when no valid subarray exists. For example:

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

The total sum of the entire array is still less than the target. A buggy implementation might accidentally return an uninitialized value or the array length. This implementation avoids that problem by initializing min_length to infinity and returning 0 if it was never updated.

Another important case is when a single element already satisfies the target. For example:

target = 4
nums = [1,4,4]

Some implementations incorrectly continue expanding the window without shrinking immediately, which can miss the optimal answer of 1. The inner while loop guarantees that the window is minimized as soon as it becomes valid.

A third edge case occurs when the entire array is required to meet the target. For example:

target = 15
nums = [1,2,3,4,5]

The algorithm must correctly handle windows that grow to cover the full array. Since the sliding window expands progressively and only shrinks when valid, it naturally supports this case without any special handling.

Another subtle case involves repeated small numbers:

target = 3
nums = [1,1,1,1,1]

Here, many overlapping windows exist with the same sum. Incorrect pointer movement can accidentally skip candidate windows. Because this implementation moves the left pointer one step at a time while the condition remains satisfied, every minimal valid window is considered correctly.