Shortest Subarray with Sum at Least K

1. Define the problem

Shortest Subarray with Sum at Least K

Given an integer array nums, which may include negative numbers , and an integer k, find the length of the shortest contiguous subarray with sum at least k . Return -1 if no such subarray exists. A plain converging window doesn't work once negatives are allowed, since the sum stops being monotonic — this calls for a monotonic deque over prefix sums instead, the natural extension of the sliding-window idea.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums_i ≤ 10⁵
1 ≤ k ≤ 10⁹

Example

Inputnums = [2,-1,2], k = 3

Output3

Explanation The whole array sums to 3, and no shorter contiguous subarray reaches sum ≥ 3.

2. Know the words first

In plain terms

Subarray: A run of elements taken right out of the array as-is, next to each other in order — not values picked out from anywhere in the array.

3. Visualize the solution

A monotonic deque of prefix sums

prefix[0]0

prefix[1]2

prefix[2]1

prefix[3]3

StatusPush

prefix[0] = 0 — deque is empty, push index 0.

What happens in this step

prefix[0] = 0
deque = []  → nothing to pop (front or back)
push index 0 → deque = [0]

Step 1 of 5

Steps to visualize

Because nums can hold negatives, growing or shrinking a plain window doesn't reliably help or hurt — this needs prefix sums instead.
Build prefix_i as the sum of the first i elements, so any subarray sum is a difference of two prefix values.
For each new prefix sum, pop from the front of the deque while that gap already reaches sum ≥ k, recording the length.
Pop from the back while its prefix sum is ≥ the current one — a smaller, more recent prefix is always at least as useful going forward.
Push the current index onto the back and continue scanning.
Return the shortest length recorded, or -1 if the deque never produced one.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

A monotonic deque of prefix sums

prefix[0]0

prefix[1]2

prefix[2]1

prefix[3]3

StatusPush

prefix[0] = 0 — deque is empty, push index 0.

What happens in this step

prefix[0] = 0
deque = []  → nothing to pop (front or back)
push index 0 → deque = [0]

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function shortestSubarray(nums, k) {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

  const deque = [];
  let best = Infinity;

  for (let i = 0; i <= n; i++) {
    while (deque.length > 0 && prefix[i] - prefix[deque[0]] >= k) {
      best = Math.min(best, i - deque.shift());
    }

    while (deque.length > 0 && prefix[deque[deque.length - 1]] >= prefix[i]) {
      deque.pop();
    }

    deque.push(i);
  }

  return best === Infinity ? -1 : best;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [2,-1,2], k = 3`	`3`	Docstring example
`nums = [1], k = 1`	`1`	k satisfied by the only element
`nums = [1,2], k = 4`	`-1`	Impossible — total sum never reaches k
`nums = [-1,-2,-3], k = 1`	`-1`	All negative numbers, always impossible
`nums = [1,1,1,1], k = 4`	`4`	k requires the entire array
`nums = [3,-2,5], k = 5`	`1`	k satisfied by a single element in the middle
`nums = [84,-37,32,40,95], k = 167`	`3`	Larger hand-verified case with negatives

Shortest Subarray with Sum at Least K