Minimum size subarray sum

Given an array of positive integers nums and a positive integer target, return the length of the shortest contiguous subarray whose sum is at least target, or 0 if no subarray reaches it. Aim for O(n) time and O(1) extra space.

Interface

Unless you agree on a different interface with the interviewer, assume:

• min_subarray_len(target: int, nums: list[int]) -> int

Example

min_subarray_len(7, [2, 3, 1, 2, 4, 3])        ->  2     # [4, 3]
min_subarray_len(4, [1, 4, 4])                 ->  1     # [4]
min_subarray_len(11, [1, 1, 1, 1, 1, 1, 1, 1]) ->  0     # the whole array sums to 8

Constraints

• 1 <= len(nums) <= 10^5; 1 <= nums[i] <= 10^4; 1 <= target <= 10^9.

Clarifying questions

• Are all values strictly positive?
• Is the condition "at least" or "exactly" target?
• What should be returned when no subarray qualifies?

What a strong answer covers

• Two pointers: add nums[right] to a running sum; while the sum is at least target, record the window length and remove nums[left].
• Why it is correct: with positive values the sum only grows as the window extends and only shrinks as it narrows, so no shorter window is skipped.
• O(n) time, as each index enters and leaves once; O(1) space; a sentinel of n + 1 turned into 0 at the end.
• Tests with the examples, a single element that meets the target and a target larger than the total.

Follow-ups

• An O(n log n) version with prefix sums and binary search.
• Values may be negative: the window no longer works; use prefix sums with a monotonic deque.
• Return the subarray's start and end, not just its length.