Shortest Subarray - Implementation

You'll use a deque to maintain candidate starting positions. The core idea: if $prefix[j] \geq prefix[i]$ and $j > i$, position $i$ is never useful.

For each position $j$, you do two things. First, remove positions from the back of the deque whose prefix sum is $\geq prefix[j]$. They will never be optimal starting points because $j$ is closer and has a smaller or equal prefix sum. Second, check positions at the front of the deque: while $prefix[j] - prefix[front] \geq k$, you have a valid subarray. Update your answer with $j - front$, then pop the front (no future $j$ will do better with that index).

Each position enters the deque once and leaves once. This gives $O(n)$ total work across all iterations.

Time complexity: $O(n)$.

Space complexity: $O(n)$ for the prefix array and deque.