Algorithm
Problem Name: 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 <= 105-105 <= nums[i] <= 1051 <= k <= 109
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const shortestSubarray = function(nums, k) {
const q = [], n = nums.length
let res = Infinity, sum = 0
const prefix = []
for(let i = 0; i < n; i++) {
sum += nums[i]
prefix.push(sum)
if(sum >= k) res = Math.min(res, i + 1)
}
for(let i = 0; i < n; i++) {
while(q.length && prefix[i] < = prefix[q[q.length - 1]]) q.pop(>
while(q.length && prefix[i] - prefix[q[0]] >= k) {
res = Math.min(res, i - q[0])
q.shift()
}
q.push(i)
}
return res === Infinity ? -1 : res
};
Input
nums = [1], k = 1
Output
1
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def shortestSubarray(self, A, K):
heap, l, sm = [], float("inf"), 0
heapq.heappush(heap, (0, -1))
for i, num in enumerate(A):
sm += num
dif = sm - K
while heap and (heap[0][0] <= dif or i - heap[0][1] >= l):
preSum, preIndex = heapq.heappop(heap)
if i - preIndex < l:
l = i - preIndex
heapq.heappush(heap, (sm, i))
return l < float("inf") and l or -1
Input
nums = [1], k = 1
Output
1