Shortest Subarray With Sum at Least K
Mahabharata — The Deque of Generals — Minimum Regiment That Breaks Karna's Defense
न्यूनतमेन बलेन यः कार्यं सिद्धयति। क्रमेण क्षीणान् मुक्त्वा दृढां सेनां रचयेत्॥
*One who accomplishes the task with minimum force succeeds. Release the diminished ones in order — build the strong regiment.*
The Story
sw-2 solved minimum subarray sum for POSITIVE arrays. But what if the array contains negative numbers? The sliding window shrink logic breaks — removing a negative from the left could INCREASE the sum, invalidating the while-loop invariant.
Krishna posed the harder version to Arjuna during a strategy session: the valor array contains both positive AND negative values. The target K must be reached with the shortest contiguous regiment.
"For positive-only arrays, sw-2 works beautifully," Krishna said. "But with negatives, we need a fundamentally different approach: prefix sums plus a monotone deque."
**The insight:** Build the prefix sum array `pre[]` where `pre[i] = sum of first i elements`. We want the shortest subarray [j..i-1] with sum ≥ K, i.e., `pre[i] - pre[j] >= K`, i.e., `pre[j] <= pre[i] - K`.
For each index i (right boundary), we want the LARGEST j with `pre[j] <= pre[i] - K` — giving the longest right endpoint while minimizing subarray length.
**Monotone deque of indices (increasing prefix sums):** - Maintain a deque where `pre[deque[0]] <= pre[deque[1]] <= ...` - For each i: pop from FRONT while `pre[i] - pre[deque.front] >= K` → valid subarray, record minimum length and pop (can't do better with this j) - Pop from BACK while `pre[deque.back] >= pre[i]` → this back index will never be optimal (current i has smaller prefix sum, so using i as j is always at least as good)
Krishna traced through `nums = [2, -1, 2]`, K = 3: pre = [0, 2, 1, 3]
Deque = [] - i=0: pre[0]=0. Back pop (none). Push 0. Deque=[0] - i=1: pre[1]=2. Front: pre[1]-pre[0]=2<3. Back: pre[0]=0<2, no pop. Push 1. Deque=[0,1] - i=2: pre[2]=1. Front: pre[2]-pre[0]=1<3. Back: pre[1]=2>pre[2]=1 → pop 1. pre[0]=0<1, no pop. Push 2. Deque=[0,2] - i=3: pre[3]=3. Front: pre[3]-pre[0]=3>=3! len=3-0=3. Pop 0. Deque=[2]. Front: pre[3]-pre[2]=3-1=2<3. No more valid. Push 3. Deque=[2,3]
Answer: 3 (entire array [2,-1,2] = 3 ≥ K).
"The deque's monotone property ensures we never miss an optimal j," Krishna explained. "We pop from the back when a new prefix is smaller — those larger old prefixes are dominated (same or later start, smaller contribution). We pop from the front when we find valid subarrays — once used as a left boundary, they can only give longer subarrays going forward."
Arjuna internalized the technique. The minimum regiment of valor K — even across a battlefield with strategic retreats (negative values) — could be found in O(n log n) time.
This is the Prefix Sum with Monotone Deque technique for shortest subarray with negative numbers allowed.
Arjuna's First Instinct
Try all start-end pairs. Compute sum. Track minimum length where sum ≥ K. O(n²) time.
public int shortestSubarrayBruteForce(int[] nums, int k) {
int minLen = Integer.MAX_VALUE;
for (int s = 0; s < nums.length; s++) {
long sum = 0;
for (int e = s; e < nums.length; e++) {
sum += nums[e];
if (sum >= k) { minLen = Math.min(minLen, e - s + 1); break; }
}
}
return minLen == Integer.MAX_VALUE ? -1 : minLen;
}Krishna's Deque Wisdom
public int shortestSubarray(int[] nums, int k) {
int n = nums.length, minLen = n + 1;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
// Pop front: valid subarrays ending at i
while (!dq.isEmpty() && pre[i] - pre[dq.peekFirst()] >= k) {
minLen = Math.min(minLen, i - dq.pollFirst());
}
// Pop back: maintain increasing prefix sums
while (!dq.isEmpty() && pre[dq.peekLast()] >= pre[i]) {
dq.pollLast();
}
dq.addLast(i);
}
return minLen <= n ? minLen : -1;
}Step-by-Step Walkthrough
nums=[84,-37,32,40,95], k=167 pre=[0,84,47,79,119,214] i=0: dq=[] i=1(84): no front valid. push→dq=[0] i=2(47): pre[0]=0<47, no backpop. push→dq=[0,1] Wait: pre[1]=84>pre[2]=47→ pop 1! dq=[0]. push 2→dq=[0,2] i=3(79): pre[2]=47<79, no backpop. push→dq=[0,2,3] i=4(119): front: 119-0=119<167. push→dq=[0,2,3,4] i=5(214): front: 214-0=214>=167→len=5, pop 0. front: 214-47=167>=167→len=5-2=3, pop 2. front: 214-79=135<167. push→dq=[3,4,5] Return 3 ✅
Deep Insight
**Why can we pop the front after finding a valid window?** Once we use index j as a left boundary for right boundary i and get length (i-j), using j for any future i' > i would give length (i'-j) > (i-j). We already found the minimum contribution from j.
**Why pop the back when pre[back] >= pre[i]?** If pre[back] >= pre[i], then for any future right boundary r: `pre[r] - pre[i] >= pre[r] - pre[back]`. Using i as the left boundary always gives a larger (or equal) difference than using back. So back is dominated.
**Why O(n log n) and not O(n)?** The deque operations themselves are O(n) amortized. But building the prefix sum is O(n) and the overall algorithm is O(n). Some implementations use sorted structures for O(n log n). Pure deque approach is O(n).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All pairs checked |
| Optimal | O(n) | O(n) | Each index pushed and popped from deque at most once |
Pattern Recognition
✅ Minimum length subarray with sum ≥ K ✅ Array contains NEGATIVE numbers (sliding window won't work) ✅ Prefix sum + monotone deque ✅ O(n) amortized via deque pop operations **LeetCode Trigger Phrases:** → "shortest subarray" + "negative numbers" + sum → "minimum length subarray" where sliding window fails → "prefix sum" + "monotone deque"
Bhagavad Gita 12.17
यो न हृष्यति न द्वेष्टि न शोचति न काङ्क्षति। शुभाशुभपरित्यागी भक्तिमान्यः स मे प्रियः॥
One who neither rejoices nor grieves, neither laments nor desires, who has renounced both good and evil — such a devoted person is dear to Me.
Connection: The deque maintains equanimity — it neither clings to large prefix sums (pops them when dominated) nor holds onto promising old starts beyond their usefulness (pops them when consumed). Like the devotee who releases both the pleasant and unpleasant with equal grace, the deque releases each index at precisely the right moment — neither too early nor too late.