Practice/Toast/Leetcode 209. Minimum Size Subarray Sum

Leetcode 209. Minimum Size Subarray Sum

CodingMust

Problem

Given an array of positive integers and a target value, find the minimal length of a contiguous subarray whose sum is greater than or equal to the target. If no such subarray exists, return 0.

A subarray is a contiguous sequence of elements within the array.

Requirements

1. Find the shortest contiguous subarray with sum ≥ target
2. Return the length of this subarray
3. Return 0 if no valid subarray exists
4. All array elements are positive integers

Constraints

• 1 ≤ nums.length ≤ 105
• 1 ≤ nums[i] ≤ 104
• 1 ≤ target ≤ 109
• Aim for O(n) time complexity
• O(1) extra space complexity preferred

Examples

Example 1:

Input: target = 7, nums = [2, 3, 1, 2, 4, 3] Output: 2 Explanation: The subarray [4, 3] has the minimal length of 2 under the constraint that its sum equals 7.

Example 2:

Input: target = 4, nums = [1, 4, 4] Output: 1 Explanation: A single element (4) already meets the target.

Example 3:

Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1] Output: 0 Explanation: The sum of the entire array is 8, which is less than 11. No valid subarray exists.