Code Implementation

from collections import deque

class Solution:
    def shortestSubarray(self, nums, k):
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        dq = deque()
        res = n + 1
        for i in range(n + 1):
            while dq and prefix[i] - prefix[dq[0]] >= k:
                res = min(res, i - dq.popleft())
            while dq and prefix[i] <= prefix[dq[-1]]:
                dq.pop()
            dq.append(i)
        return res if res <= n else -1
      

#include <vector>
#include <deque>
#include <climits>
using namespace std;

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i];
        deque<int> dq;
        int res = n + 1;
        for (int i = 0; i <= n; ++i) {
            while (!dq.empty() && prefix[i] - prefix[dq.front()] >= k) {
                res = min(res, i - dq.front());
                dq.pop_front();
            }
            while (!dq.empty() && prefix[i] <= prefix[dq.back()])
                dq.pop_back();
            dq.push_back(i);
        }
        return res <= n ? res : -1;
    }
};
      

import java.util.*;

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + nums[i];
        Deque<Integer> dq = new ArrayDeque<>();
        int res = n + 1;
        for (int i = 0; i <= n; ++i) {
            while (!dq.isEmpty() && prefix[i] - prefix[dq.peekFirst()] >= k) {
                res = Math.min(res, i - dq.pollFirst());
            }
            while (!dq.isEmpty() && prefix[i] <= prefix[dq.peekLast()])
                dq.pollLast();
            dq.addLast(i);
        }
        return res <= n ? res : -1;
    }
}
      

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i)
        prefix[i + 1] = prefix[i] + nums[i];
    const dq = [];
    let res = n + 1;
    for (let i = 0; i <= n; ++i) {
        while (dq.length && prefix[i] - prefix[dq[0]] >= k) {
            res = Math.min(res, i - dq.shift());
        }
        while (dq.length && prefix[i] <= prefix[dq[dq.length - 1]])
            dq.pop();
        dq.push(i);
    }
    return res <= n ? res : -1;
};
      

Problem Description

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

• Each subarray must be contiguous (elements next to each other in the original array).
• Elements cannot be reused; each subarray is a slice of the original array.
• There may be negative numbers in nums.
• There is not guaranteed to be a valid solution.

Thought Process

The first instinct might be to check all possible subarrays and find the shortest one whose sum is at least k. However, this brute-force approach is inefficient, especially for long arrays, because it requires checking every possible subarray.

For positive numbers, a sliding window works well, but negative numbers break the simple sliding window logic, because removing a negative number could increase the sum. So, we need a strategy that works even with negative numbers.

To optimize, we can use prefix sums to quickly calculate subarray sums, and a data structure (like a deque) to efficiently track candidates for the start of our subarray as we scan through the array.

Solution Approach

Our optimized solution uses prefix sums and a monotonic queue (deque) to efficiently find the shortest qualifying subarray.

1. Compute Prefix Sums:
   • Create an array prefix where prefix[i] is the sum of nums[0] to nums[i-1].
   • Any subarray sum from i to j-1 is prefix[j] - prefix[i].
2. Use a Deque to Track Candidates:
   • The deque stores indices of prefix in increasing order.
   • For each new index i, we check if prefix[i] - prefix[dq[0]] >= k. If so, we found a subarray from dq[0] to i-1 with sum at least k.
   • We remove elements from the back of the deque if prefix[i] is less than or equal to prefix[dq[-1]], since they can't help us find a shorter subarray in the future.
3. Iterate Through Prefix Sums:
   • For each position, process the deque as above, and update the shortest length found.
4. Return the Result:
   • If we found a valid subarray, return its length. Otherwise, return -1.

The deque ensures we efficiently keep track of the best candidates for the start of a valid subarray, and prefix sums let us compute subarray sums in constant time.

Example Walkthrough

Suppose nums = [2, -1, 2] and k = 3.

1. Compute prefix sums: [0, 2, 1, 3]
2. Initialize deque: empty, result = 4 (n+1)
3. For i = 0:
   • Deque empty, append 0.
4. For i = 1:
   • prefix[1] - prefix[0] = 2 - 0 = 2 < 3
   • Append 1 to deque.
5. For i = 2:
   • prefix[2] - prefix[0] = 1 - 0 = 1 < 3
   • prefix[2] <= prefix[1], so remove 1 from back.
   • Append 2 to deque.
6. For i = 3:
   • prefix[3] - prefix[0] = 3 - 0 = 3 >= 3, so subarray [0,2] is valid, length 3.
   • Update result to 3, remove 0 from front.
   • prefix[3] - prefix[2] = 3 - 1 = 2 < 3, so stop.
   • Append 3 to deque.
7. Final answer is 3 (the entire array). If there were a shorter valid subarray, the algorithm would have found it.

Time and Space Complexity

• Brute-force approach:
  • O(N²) time for checking all subarrays.
  • O(1) extra space.
• Optimized approach (prefix sums + deque):
  • O(N) time, since each index is added and removed from the deque at most once.
  • O(N) space for the prefix sums and deque.

The optimized approach is much faster for large arrays, especially when negative numbers are present.

Summary

To solve the "Shortest Subarray with Sum at Least K" problem efficiently, we use prefix sums to quickly calculate subarray sums and a monotonic deque to track the best starting points for subarrays. This approach handles negative numbers and finds the shortest qualifying subarray in linear time. The key insight is using the deque to maintain a list of candidates in increasing order, discarding those that can never lead to a shorter or better subarray. This results in a clean, elegant, and highly efficient solution.