862. Shortest Subarray with Sum at Least K

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.
 

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• $1<=nums.length<=10^5$
• $-10^5<=nums[i]<=10^5$
• $1<=k<=10^9$

From: LeetCode
Link: 862. Shortest Subarray with Sum at Least K

Solution:

Ideas:

• Prefix sum: Build an array pref[] where pref[i] = sum of first i elements.

• Key observation: Subarray sum from j to i-1 = pref[i] - pref[j].

• Goal: Find smallest (i - j) such that pref[i] - pref[j] >= k.

• Deque: Use a monotonic deque to store candidate indices j with increasing pref[j].

• Two rules:

  • Pop from front while condition satisfied (pref[i] - pref[dq[front]] >= k) → update answer.
  • Pop from back while current prefix ≤ last in deque (pref[i] <= pref[dq[back]]) → maintain increasing order.

• Result: The deque ensures we check only useful candidates, giving O(n) time.

• Final check: If answer ≤ numsSize, return it; else return -1.

Code:

int shortestSubarray(int* nums, int numsSize, int k) {
    // Prefix sums: pref[i] = sum of nums[0..i-1]
    long long *pref = (long long*)malloc((numsSize + 1) * sizeof(long long));
    pref[0] = 0;
    for (int i = 0; i < numsSize; ++i) pref[i + 1] = pref[i] + nums[i];

    // Monotonic deque of indices into pref[], storing increasing prefix sums
    int *dq = (int*)malloc((numsSize + 1) * sizeof(int));
    int head = 0, tail = 0;

    int ans = numsSize + 1;

    for (int i = 0; i <= numsSize; ++i) {
        // Try to shrink from the front while we meet the >= k condition
        while (head < tail && pref[i] - pref[dq[head]] >= k) {
            int len = i - dq[head];
            if (len < ans) ans = len;
            head++;
        }
        // Maintain increasing prefix sums in deque
        while (head < tail && pref[i] <= pref[dq[tail - 1]]) {
            tail--;
        }
        dq[tail++] = i;
    }

    free(pref);
    free(dq);
    return (ans <= numsSize) ? ans : -1;
}