Sliding Window — Shortest Subarray with Sum at Least K

↗ LeetCode: Shortest Subarray with Sum at Least K · Hard · pattern chapter →

Asked atAmazonGoogle

Smallest subarray sum ≥ k. Array may contain negatives.

Example 1 — nums=[1], k=1 → 1Example 2 — nums=[1,2], k=4 → -1Example 3 — nums=[2,-1,2], k=3 → 3

Constraints — 1 ≤ n ≤ 10⁵; -10⁵ ≤ nums[i] ≤ 10⁵. Brute enumerates all subarrays — O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Prefix sum + monotonic deque is O(n) = 10⁵ ops = <10 ms.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Sliding window fails

With negatives, sum isn't monotone in window size — can't shrink safely.

Approach 2 — Prefix sums + monotonic deque (canonical)

Insight. Define P[i] = prefix sum. Answer = min j - i with P[j] - P[i] ≥ k. For each j, find earliest i < j with P[i] ≤ P[j] - k.

Maintain a deque of candidate i where P is increasing:

Pop front while P[deque.front] ≤ P[j] - k — record candidate and discard.
Pop back while P[deque.back] ≥ P[j] — later smaller prefix dominates.

java

int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] P = new long[n + 1];
    for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
    Deque<Integer> dq = new ArrayDeque<>();
    int best = Integer.MAX_VALUE;
    for (int j = 0; j <= n; j++) {
        while (!dq.isEmpty() && P[j] - P[dq.peekFirst()] >= k)
            best = Math.min(best, j - dq.pollFirst());
        while (!dq.isEmpty() && P[dq.peekLast()] >= P[j]) dq.pollLast();
        dq.offerLast(j);
    }
    return best == Integer.MAX_VALUE ? -1 : best;
}

Execution Trace

Deque on prefix — nums=[2,-1,2], k=3

Step 1 / 3P=[0,2]

Complexity — Time O(n); Space O(n).

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Sliding window	fails	—	rejected (negatives)
Monotonic deque	O(n)	O(n)	canonical

When to use which

Positives only → sliding window fine.
Negatives allowed → monotonic deque on prefix sums.
"Longest" instead → different template — deque with reverse condition.

✨AI Study CompanionBeta

Minimum Size Subarray Sum — positives only
Constrained Subsequence Sum
Sliding Window Maximum

Was this page helpful?

📚 Related problems

Sliding Window — Shortest Subarray with Sum at Least K ​

Approach 1 — Sliding window fails ​

Approach 2 — Prefix sums + monotonic deque (canonical) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​