Shortest Subarray with Sum at Least K

Shortest Subarray with Sum at Least K

What is this problem about?

The Shortest Subarray with Sum at Least K interview question gives you an integer array that may contain negative numbers and an integer K. Find the length of the shortest contiguous subarray whose sum is at least K. If no such subarray exists, return -1. The presence of negative numbers makes this much harder than the positive-only sliding window version and requires a monotonic deque with prefix sums.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this HARD problem because it is the canonical application of a monotonic deque on prefix sums. With only positive numbers, a simple two-pointer works. But negative numbers break the monotone property of the sliding window sum — necessitating the deque-based approach. It tests deep understanding of when and why deque-based optimization is needed over simpler techniques.

Algorithmic pattern used

The pattern is prefix sum + monotonic deque. Compute prefix sums P[i] where P[0]=0 and P[i] = P[i-1] + nums[i-1]. Finding a subarray nums[i..j] with sum ≥ K is equivalent to finding P[j+1] - P[i] >= K, i.e., P[j+1] >= P[i] + K. Use a monotonic deque of indices with increasing prefix sums: for each new index j, pop from the front while P[j] - P[deque.front()] >= K (found a valid subarray — track minimum length). Then pop from the back while P[j] <= P[deque.back()] (maintain monotone increasing order). Push j to the back.

Example explanation

nums = [2, -1, 2], K = 3.

Prefix sums: P = [0, 2, 1, 3].

Deque processing:

• j=0: P[0]=0. Deque=[0].
• j=1: P[1]=2. 2-0=2 < 3. Deque=[0,1].
• j=2: P[2]=1. 1 ≤ P[1]=2 → pop 1. Deque=[0,2].
• j=3: P[3]=3. 3-P[0]=3 ≥ 3 → window [1,3], length=3. Pop 0. Deque=[2]. 3-P[2]=3-1=2 < 3.

Minimum length: 3 (entire array).

Common mistakes candidates make

• Using a simple two-pointer — doesn't work when negative numbers are present (window sum isn't monotone).
• Not building prefix sums of size n+1 — the deque operates on prefix sums including P[0]=0.
• Popping from the back when P[j] < P[deque.back()] incorrectly — pop when <= to maintain strictly increasing deque.
• Not tracking the minimum length when popping from the front.

Interview preparation tip

For the Shortest Subarray with Sum at Least K coding problem, the monotonic queue prefix sum array interview pattern is the O(n) solution. The deque maintains indices with increasing P values — when P[j] - P[front] >= K, the front index gives the farthest valid left boundary, and popping the front reveals the next candidate. Goldman Sachs and Bloomberg interviewers test whether you know why the simple sliding window fails here. Practice the P[j] - P[i] >= K reformulation as the key that unlocks the monotonic deque approach for this problem class.