Shortest Reaching Subarray (Negatives) — Solution & Editorial

Back to the Problem

With negatives the sliding window fails. Use prefix sums and a monotonic deque: maintain increasing prefix values; for each i pop from the front while pre[i]−pre[front] ≥ K (recording lengths), and pop the back while it is not smaller than pre[i].

Complexity: O(N)

Watch out: The positive-values two-pointer method is wrong here — the deque of prefix minima is required.