#862 Shortest Subarray with Sum at Least K

frequently reported atGoldman Sachs Amazon Google

the problem

In plain words

Return the length of the shortest non-empty subarray of nums whose sum is at least k, or −1 if none exists. nums may contain negative numbers.

in nums = [1], k = 1

out 1

in nums = [1,2], k = 4

out -1

in nums = [2,-1,2], k = 3

out 3

1 ≤ n ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ 10⁹

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

With prefix sums P, a subarray (i, j] works when P[j] − P[i] ≥ k. Keep candidate starts i in a deque with increasing P. A start with a larger P than a later one is useless; a start that already succeeded can retire, because later ends are only longer.

solutions

From brute force to optimal

For each start, add elements until the sum ≥ k; record the length.

For each i: running sum over j = i, i+1, …
On the first sum ≥ k, record j − i + 1 and stop that start.

timeO(n²)

n starts, each may scan to the end.

spaceO(1)

A running sum (as long).

javajava.util.*

1class Solution {2    public int shortestSubarray(int[] nums, int k) {3        int n = nums.length;4        int best = Integer.MAX_VALUE;5        for (int i = 0; i < n; i++) {6            long sum = 0;7            for (int j = i; j < n; j++) {8                sum += nums[j];9                if (sum >= k) {10                    best = Math.min(best, j - i + 1);11                    break; // longer subarrays from the same start can't be shorter12                }13            }14        }15        return best == Integer.MAX_VALUE ? -1 : best;16    }17}

For each end j: pop good starts from the front (recording lengths), pop worse starts from the back, then add j.

Build long prefix sums P[0..n].
For j = 0..n: while P[j] − P[front] ≥ k, record j − front and poll the front.
While P[back] ≥ P[j], poll the back (j is a later, lower start — strictly better).
Offer j.

timeO(n)

Each prefix index enters and leaves the deque at most once.

spaceO(n)

The prefix array and the deque.

javajava.util.*

1class Solution {2    public int shortestSubarray(int[] nums, int k) {3        int n = nums.length;4        long[] prefix = new long[n + 1]; // sum(nums[i..j-1]) = prefix[j] - prefix[i]5        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];6        int best = n + 1;7        Deque<Integer> dq = new ArrayDeque<>(); // start candidates, prefix values increasing8        for (int j = 0; j <= n; j++) {9            while (!dq.isEmpty() && prefix[j] - prefix[dq.peekFirst()] >= k) {10                best = Math.min(best, j - dq.pollFirst()); // later ends would only be longer: retire it11            }12            while (!dq.isEmpty() && prefix[dq.peekLast()] >= prefix[j]) {13                dq.pollLast(); // j starts later with a smaller-or-equal prefix: always better14            }15            dq.offerLast(j);16        }17        return best <= n ? best : -1;18    }19}

in the room

How to say it in the interview

talk track

Say why the sliding window from the Sliding Window chapter fails: with negatives, shrinking the window can increase the sum.
Explain both pop rules separately — front pops are about answers, back pops are about dominance.

traps

Using int prefix sums — 10⁵ × 10⁵ = 10¹⁰ overflows.
Using a two-pointer window, which is only correct for non-negative numbers (LC 209).

what they ask next

Follow-ups

All numbers non-negative?

Then a plain sliding window works in O(n) with O(1) space — that's LC 209 Minimum Size Subarray Sum.

before you submit

Edge cases to test

No subarray reaches k (for example, all negative numbers) → −1.
One element ≥ k on its own → 1.
Prefix sums can pass 2³¹ − 1 (10⁵ values of 10⁵), so store them as long.
Negatives break the two-pointer window: shrinking it can raise the sum.

practise next