Here's the solution:
function shortestSubarray(nums, k)
n := length of nums
prefix := array of size (n + 1)
prefix[0] := 0
for i from 0 to n - 1
prefix[i + 1] := prefix[i] + nums[i]
deque := empty deque // stores indices into prefix
minLength := infinity
for j from 0 to n
// Check valid subarrays from front
while deque is not empty and prefix[j] - prefix[front of deque] >= k
minLength := min(minLength, j - front of deque)
pop front from deque
// Maintain increasing order
while deque is not empty and prefix[j] <= prefix[back of deque]
pop back from deque
push j to back of deque
if minLength = infinity
return -1
return minLength
Time: . Space: .