Shortest Subarray - Algorithm

Maintain a monotonic increasing deque of indices (by prefix sum value):

$1.$ For each $j$, pop from front while $prefix[j] - prefix[deque.front()] \geq k$. Each such index gives a valid subarray. Record the shortest.

$2.$ Pop from back while $prefix[j] \leq prefix[deque.back()]$. These indices are dominated and never useful.

$3.$ Push $j$ to back. The front removal is different from sliding window max. Once an index gives a valid answer, it can't give a shorter answer for any later $j$, so you remove it. Time: $O(n)$. Space: $O(n)$.