862. Shortest Subarray with Sum at Least K

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.

 

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 <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

 

Solutions

Solution: Prefix Sum + Monotonic Queue

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const shortestSubarray = function (nums, k) {
  const n = nums.length;
  const prefixSum = new Array(n).fill(0);
  const monotonicQueue = [-1];
  let result = n + 1;

  prefixSum[-1] = 0;

  for (let index = 0; index < n; index++) {
    prefixSum[index] = nums[index] + prefixSum[index - 1];
  }
  for (let index = 0; index < n; index++) {
    const sum = prefixSum[index];

    while (monotonicQueue.length && sum - prefixSum[monotonicQueue[0]] >= k) {
      result = Math.min(index - monotonicQueue[0], result);
      monotonicQueue.shift();
    }
    while (monotonicQueue.length && sum <= prefixSum[monotonicQueue.at(-1)]) {
      monotonicQueue.pop();
    }
    monotonicQueue.push(index);
  }
  return result === n + 1 ? -1 : result;
};