Shortest Subarray - Implementation

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: $O(n)$. Space: $O(n)$.