Minimum Size Subarray Sum

Given an array of positive integers nums and a target sum, return the minimal length of a contiguous subarray whose sum is at least the target. If there is no such subarray, return 0.

Because all numbers are positive, a sliding window works in O(n).

Function signature

func MinSubArrayLen(target int, nums []int) int

Inputs / outputs

• target: required minimum sum.
• nums: slice of positive integers.
• Return: minimal subarray length, or 0 if none.

Example

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

Reason: [4,3] is the shortest window with sum >= 7.

Constraints

• 0 <= len(nums) <= 100_000
• 1 <= nums[i] <= 1_000_000_000
• 1 <= target <= 1_000_000_000

Core idea (near-solution)

Use a sliding window [l, r] with a running sum.

• Expand r to increase the sum.
• When the sum is >= target, shrink from the left to find the minimal window.

Invariant: the sum always equals the elements inside the current window.

Algorithm (step-by-step)

1. Initialize l = 0, sum = 0, best = +infinity.
2. For each r from 0 to len(nums)-1:
   • Add nums[r] to sum.
   • While sum >= target:
     • Update best = min(best, r-l+1).
     • Subtract nums[l] from sum and increment l.
3. If best was never updated, return 0; otherwise return best.

Correctness sketch

• Invariant: the sum always equals the elements inside the current window.
• The window state exactly matches the elements in s[l..r].
• Shrinking/expanding preserves validity, so any recorded window is correct.
• The best recorded window is optimal because all candidate windows are considered.

Trace (hand walkthrough)

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

Reason: [4,3] is the shortest window with sum >= 7.

Walk:
- r=0 sum=2; r=1 sum=5; r=2 sum=6
- r=3 sum=8 >=7 -> min=4, shrink: drop 2 -> sum=6, l=1
- r=4 sum=10 >=7 -> min=4, drop 3 -> sum=7, l=2 -> min=3; drop 1 -> sum=6, l=3
- r=5 sum=9 >=7 -> min=3, drop 2 -> sum=7, l=4 -> min=2; drop 4 -> sum=3

Pitfalls to avoid

• Forgetting to shrink while sum >= target (must be a loop, not an if).
• Using this approach if numbers can be negative (it breaks the invariant).

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Maintain sum and left; shrink while sum >= target.
• Track the smallest window; return 0 if no valid window.