The problem
Find the length of the shortest contiguous subarray with sum ≥ k. Values may be NEGATIVE. Return −1 if none exists.
Stuck? Reveal hints one at a time
How to approach it
- 1Compute prefix sums P[0..n] (P[0] = 0).
- 2Scan j left to right. While P[j] − P[front] ≥ k: record j − front as a candidate and pop the front (it can never do better later).
- 3While P[back] ≥ P[j]: pop the back — a later, no-larger prefix dominates it as a start point.
- 4Push j. Minimum candidate wins; −1 if none.
Key insight
Two separate monotonic evictions: the front pops when SATISFIED (shorter answers later are impossible), the back pops when DOMINATED (higher prefix + earlier index is strictly worse).
The solution
Watch out for
- This is NOT Sliding Window Maximum with a different comparison — the two eviction rules serve different purposes and both are required.
- Iterate j through n (inclusive) over the prefix array, not n − 1.