Practice/Meta/Leetcode 862. Shortest Subarray with Sum at Least K

Leetcode 862. Shortest Subarray with Sum at Least K

CodingOptional

Problem

Given an array of integers (which may contain negative values) and a target sum, find the length of the shortest contiguous subarray whose sum is at least the target value. If no such subarray exists, return -1.

Unlike traditional sliding window problems where all elements are positive, the presence of negative numbers means that expanding the window doesn't guarantee an increasing sum, and shrinking it doesn't guarantee a decreasing sum. This requires a more sophisticated approach using prefix sums and efficient data structures.

Requirements

1. Return the minimum length of any contiguous subarray with sum >= target
2. Return -1 if no valid subarray exists
3. Handle arrays containing negative, zero, and positive integers
4. Optimize for large input sizes

Constraints

• 1 ≤= nums.length ≤= 100,000
• -100,000 ≤= nums[i] ≤= 100,000
• -1,000,000,000 ≤= target ≤= 1,000,000,000
• Time complexity should be O(n) where n is the array length
• Space complexity should be O(n)

Examples

Example 1:

Input: nums = [2, 3, 1, 2, 4, 3], target = 7 Output: 2 Explanation: The subarray [4, 3] has sum 7 and is the shortest with length 2

Example 2:

Input: nums = [1, -1, 5, 3, 2], target = 5 Output: 1 Explanation: The single element [5] achieves the target with minimum length 1

Example 3:

Input: nums = [2, -1, 2, 1], target = 3 Output: 3 Explanation: The subarray [2, -1, 2] sums to 3 with length 3

Example 4:

Input: nums = [1, 2, -3, -2], target = 10 Output: -1 Explanation: No subarray can achieve a sum of 10 or greater