862. Shortest Subarray with Sum at Least K

Problem Description

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Examples:

Input: nums = [1], k = 1
Output: 1

Input: nums = [1,2], k = 4
Output: -1

Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

• 1 ≤ nums.length ≤ 10⁵
• -10⁵ ≤ nums[i] ≤ 10⁵
• 1 ≤ k ≤ 10⁹

Python Solution

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # Calculate prefix sums
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        
        # Initialize result and deque
        result = n + 1
        deque = collections.deque()
        
        # Process each prefix sum
        for i in range(n + 1):
            # Remove elements from deque that can't give shorter subarray
            while deque and prefix_sum[i] - prefix_sum[deque[0]] >= k:
                result = min(result, i - deque.popleft())
            
            # Remove elements that are larger than current prefix sum
            while deque and prefix_sum[i] <= prefix_sum[deque[-1]]:
                deque.pop()
            
            deque.append(i)
        
        return result if result <= n else -1

Implementation Notes:

• Uses monotonic deque for efficient processing
• Time complexity: O(n)
• Space complexity: O(n)

Java Solution

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        // Calculate prefix sums using long to handle large numbers
        long[] prefix_sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
        }
        
        // Initialize result and deque
        int result = n + 1;
        Deque deque = new ArrayDeque<>();
        
        // Process each prefix sum
        for (int i = 0; i <= n; i++) {
            // Remove elements from deque that can't give shorter subarray
            while (!deque.isEmpty() && prefix_sum[i] - prefix_sum[deque.peekFirst()] >= k) {
                result = Math.min(result, i - deque.pollFirst());
            }
            
            // Remove elements that are larger than current prefix sum
            while (!deque.isEmpty() && prefix_sum[i] <= prefix_sum[deque.peekLast()]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
        }
        
        return result <= n ? result : -1;
    }
}

C++ Solution

class Solution {
public:
    int shortestSubarray(vector& nums, int k) {
        int n = nums.size();
        // Calculate prefix sums using long long to handle large numbers
        vector prefix_sum(n + 1);
        for (int i = 0; i < n; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
        }
        
        // Initialize result and deque
        int result = n + 1;
        deque deque;
        
        // Process each prefix sum
        for (int i = 0; i <= n; i++) {
            // Remove elements from deque that can't give shorter subarray
            while (!deque.empty() && prefix_sum[i] - prefix_sum[deque.front()] >= k) {
                result = min(result, i - deque.front());
                deque.pop_front();
            }
            
            // Remove elements that are larger than current prefix sum
            while (!deque.empty() && prefix_sum[i] <= prefix_sum[deque.back()]) {
                deque.pop_back();
            }
            
            deque.push_back(i);
        }
        
        return result <= n ? result : -1;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function(nums, k) {
    const n = nums.length;
    // Calculate prefix sums using BigInt to handle large numbers
    const prefix_sum = new Array(n + 1).fill(0n);
    for (let i = 0; i < n; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + BigInt(nums[i]);
    }
    
    // Initialize result and deque
    let result = n + 1;
    const deque = [];
    
    // Process each prefix sum
    for (let i = 0; i <= n; i++) {
        // Remove elements from deque that can't give shorter subarray
        while (deque.length && prefix_sum[i] - prefix_sum[deque[0]] >= BigInt(k)) {
            result = Math.min(result, i - deque.shift());
        }
        
        // Remove elements that are larger than current prefix sum
        while (deque.length && prefix_sum[i] <= prefix_sum[deque[deque.length - 1]]) {
            deque.pop();
        }
        
        deque.push(i);
    }
    
    return result <= n ? result : -1;
};

C# Solution

public class Solution {
    public int ShortestSubarray(int[] nums, int k) {
        int n = nums.Length;
        // Calculate prefix sums using long to handle large numbers
        long[] prefix_sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
        }
        
        // Initialize result and deque
        int result = n + 1;
        LinkedList deque = new LinkedList();
        
        // Process each prefix sum
        for (int i = 0; i <= n; i++) {
            // Remove elements from deque that can't give shorter subarray
            while (deque.Count > 0 && prefix_sum[i] - prefix_sum[deque.First.Value] >= k) {
                result = Math.Min(result, i - deque.First.Value);
                deque.RemoveFirst();
            }
            
            // Remove elements that are larger than current prefix sum
            while (deque.Count > 0 && prefix_sum[i] <= prefix_sum[deque.Last.Value]) {
                deque.RemoveLast();
            }
            
            deque.AddLast(i);
        }
        
        return result <= n ? result : -1;
    }
}

Implementation Notes:

• Uses prefix sum array and monotonic deque
• Time complexity: O(n)
• Space complexity: O(n)