Minimum Size Subarray Sum

Explanation & Solution

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.

A subarray is a contiguous non-empty sequence of elements within an array.

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

Output: 2

Explanation: The subarray [4,3] has the minimal length under the constraint of sum >= 7.

Constraints

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

Approach

Sliding Window pattern

1. Initialize Variables

Set left = 0 as the start of the sliding window.
Set sum = 0 to track the running sum of the current window.
Set minLen = Infinity to track the smallest valid window found.

2. Expand the Window

Iterate right from 0 to nums.length - 1.
Add nums[right] to the running sum.
This grows the window to include more elements.

3. Shrink the Window When Sum is Sufficient

While sum >= target, the current window is valid.
Update minLen with the current window size right - left + 1 if it is smaller.
Subtract nums[left] from sum and increment left to try to find an even smaller valid window.

4. Return the Result

If minLen was never updated (still Infinity), no valid subarray exists — return 0.
Otherwise, return minLen.

Key Insight

This is a variable-size sliding window pattern. Because all elements are positive, the sum only increases as we expand and only decreases as we shrink. Once the sum drops below target, we stop shrinking and continue expanding. This monotonic behavior guarantees that we find the optimal window in linear time.

Time

O(n)each element is added and removed from the window at most once.

Space

O(1)only a few variables are used.

Visualization

Input:

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

—

Press ▶ or use ← → to step through

Left (L)Right (R)WindowDone

12 steps

Solution Code

Maximum Average Subarray I

Longest Substring Without Repeating Characters