LeetCode: 209. Minimum Size Subarray Sum

LeetCode: 209. Minimum Size Subarray Sum

Summary

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.

Approach

Use the sliding window technique because all numbers are positive.

For example,

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

The prefix sums are:

[2, 5, 6, 8, 12, 15]

15 - 7 = 8, and 8 appears in the prefix sums.

However, a normal prefix sum approach does not directly handle the greater than or equal to condition.

So a two-pointer sliding window approach works well here.

The right pointer always points to the current right position. We move the left pointer when the current sum of the subarray from left to right is greater than or equal to the target.

Function

Initialization:

• best = N + 1
• left = 0
• total = 0

Main: For each index i in 0..N-1: total += nums[i] while left < N and total >= target: best = min(best, i - left + 1) total -= nums[left] left += 1

Return 0 if best == N + 1; otherwise, return best.

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

1. i = 0, total = 2, do nothing.
2. i = 1, total = 5, do nothing.
3. i = 2, total = 6, do nothing.
4. i = 3, total = 8, which is greater than or equal to the target. best = 3 - 0 + 1 = 4 total = 8 - 2 = 6 left -> 1
5. i = 4, total = 10, which is greater than or equal to the target. best = 4 - 1 + 1 = 4 total = 10 - 3 = 7 left -> 2

best = 4 - 2 + 1 = 3 total = 7 - 1 = 6 left -> 3 6. i = 5, total = 9, which is greater than or equal to the target. best = 5 - 3 + 1 = 3 total = 9 - 2 = 7 left -> 4

best = 5 - 4 + 1 = 2 total = 7 - 4 = 3 left -> 5 End.

The output is 2.

Complexity

Time Complexity: O(N) because the two pointers visit each element at most once. Space Complexity: O(1)