Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Shortest Subarray with Sum at Least K

Find the shortest subarray whose sum reaches a target when negative numbers are allowed, using prefix sums and a queue of useful start positions.

Updated Medium read: 8 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n²)O(1)
Prefix sums with a queue of start positionsO(n)O(n)

The problem

Given an array of integers, which may be negative, and a positive target, return the length of the shortest run of consecutive elements whose sum is at least the target. If there is none, return -1.

numbers = [1],          target = 1   →  1
numbers = [1, 2],       target = 4   →  -1
numbers = [2, -1, 2],   target = 3   →  3    (the whole array: 2 − 1 + 2 = 3)

This is Minimum Size Subarray Sum with one change: negative numbers are allowed. That single change is what makes it hard.

Approach 1: brute force

Try every start, extending to the right.

JavaScript

function shortestSubarrayBruteForce(numbers, target) {
  let best = Infinity;
  for (let start = 0; start < numbers.length; start++) {
    let sum = 0;
    for (let end = start; end < numbers.length; end++) {
      sum += numbers[end];
      if (sum >= target) {
        best = Math.min(best, end - start + 1);
        break;
      }
    }
  }
  return best === Infinity ? -1 : best;
}

Python

def shortest_subarray_brute_force(numbers, target):
    best = float("inf")
    for start in range(len(numbers)):
        total = 0
        for end in range(start, len(numbers)):
            total += numbers[end]
            if total >= target:
                best = min(best, end - start + 1)
                break
    return -1 if best == float("inf") else best

The break is still safe: a longer subarray from the same start cannot be shorter.

Time O(n²), space O(1).

Why the sliding window fails here

With only positive numbers, a window that is too small is fixed by growing it and a window that is large enough is improved by shrinking it. Negative numbers break both rules.

Take [2, -1, 2] with a target of 3. The window grows to [2, -1], with a sum of 1. Nothing so far suggests this start is worth keeping. Then 2 arrives and the whole array sums to 3: the answer. A sliding window has no way to know whether to hold on to a start or let it go, because a later negative or positive number can change the picture either way.

Restating the problem with prefix sums

Build the prefix sums: prefix[i] is the sum of the first i elements, with prefix[0] = 0. The sum of the elements from position start up to but not including end is prefix[end] − prefix[start], and its length is end − start.

The problem becomes: find two positions start < end with

prefix[end] − prefix[start] ≥ target

that are as close together as possible. For [2, -1, 2] the prefix array is [0, 2, 1, 3].

With positive numbers the prefix array only ever rises, which is what the sliding window was quietly relying on. With negative numbers it goes up and down, and the work is in deciding which start positions are still worth remembering.

Approach 2: a queue of useful start positions

Walk end through the prefix array from left to right, keeping a queue of earlier positions that might still be the best start for some end. Two rules remove the ones that cannot be.

Rule 1: a start that has been used is finished. If prefix[end] − prefix[start] ≥ target, record the length and remove start from the front of the queue. Any later end paired with the same start would give a longer subarray, so that start can never do better than it just did.

Rule 2: a start that is beaten is useless. Before adding end to the queue as a future start, remove from the back every position whose prefix value is greater than or equal to prefix[end]. Compare such a position s with end as starting points for any later end:

  • end is further right, so the subarray is shorter.
  • prefix[end] is no larger, so the subarray's sum is at least as big.

end is better on both counts, so s will never be needed again.

Rule 2 keeps the prefix values in the queue in increasing order from front to back. That in turn is what makes Rule 1 work from the front: the front has the smallest prefix value, so it is the start most likely to reach the target, and if the front does not reach it then nothing behind it will.

JavaScript

function shortestSubarray(numbers, target) {
  const n = numbers.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + numbers[i];
 
  const starts = []; // positions in `prefix`, their values increasing
  let head = 0;      // where the front of the queue is inside `starts`
  let best = Infinity;
 
  for (let end = 0; end <= n; end++) {
    // Rule 1: starts that reach the target with this end are finished.
    while (
      head < starts.length &&
      prefix[end] - prefix[starts[head]] >= target
    ) {
      best = Math.min(best, end - starts[head]);
      head++;
    }
 
    // Rule 2: starts that this position beats are useless.
    while (
      starts.length > head &&
      prefix[starts[starts.length - 1]] >= prefix[end]
    ) {
      starts.pop();
    }
 
    starts.push(end);
  }
  return best === Infinity ? -1 : best;
}

Python

from collections import deque
 
def shortest_subarray(numbers, target):
    n = len(numbers)
    prefix = [0] * (n + 1)
    for i, value in enumerate(numbers):
        prefix[i + 1] = prefix[i] + value
 
    # Positions in `prefix`, their values increasing.
    # A deque removes from either end in constant time.
    starts = deque()
    best = float("inf")
 
    for end in range(n + 1):
        # Rule 1: starts that reach the target with this end are finished.
        while starts and prefix[end] - prefix[starts[0]] >= target:
            best = min(best, end - starts[0])
            starts.popleft()
 
        # Rule 2: starts that this position beats are useless.
        while starts and prefix[starts[-1]] >= prefix[end]:
            starts.pop()
 
        starts.append(end)
    return -1 if best == float("inf") else best

The front of the queue is removed by advancing head, not by calling shift(), which can cost O(n) on a JavaScript array.

Walkthrough

numbers = [2, -1, 2], target = 3, so prefix = [0, 2, 1, 3]. The queue is shown as positions, with their prefix values in brackets.

end prefix[end] Rule 1 Rule 2 Queue after best
0 0 0 (0) none
1 2 2 − 0 = 2, too small 0 (0), 1 (2) none
2 1 1 − 0 = 1, too small Position 1 has value 2 ≥ 1: removed 0 (0), 2 (1) none
3 3 3 − 0 = 3: record length 3, remove position 0. Then 3 − 1 = 2, too small 2 (1), 3 (3) 3

The answer is 3. At end = 2, position 1 was dropped: position 2 is a later start with a smaller prefix value, so it is the better choice for anything that follows.

Time O(n): each position is added to the queue once and removed at most once, whether from the front or the back. Space O(n) for the prefix array and the queue.

How this relates to Sliding Window Maximum

The queue here is the same structure as the one in Sliding Window Maximum: items are removed from the back when a newer item makes them redundant, and from the front when they are finished with. There the queue holds candidates for the largest value; here it holds candidates for the best start. Recognising that shape, a monotonic queue, is the real lesson of both problems.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(shortestSubarray([2, -1, 2], 3)); // 3
console.log(shortestSubarray([1, 2], 4)); // -1

Python

print(shortest_subarray([2, -1, 2], 3))  # 3
print(shortest_subarray([1, 2], 4))  # -1

The comment after each line is the result you should see.

Common mistakes

  • Using a plain sliding window. It returns wrong answers once negative numbers appear; [2, -1, 2] with target 3 is the smallest test.
  • Looping end only to n − 1. The prefix array has n + 1 entries, and the last one is needed for subarrays that reach the end of the input.
  • Applying only one of the two rules. Without Rule 2 the queue is not in order and Rule 1 can stop too early. Without Rule 1 the answer is still correct but the queue never shrinks from the front and the work is no longer linear.
  • Running Rule 2 before Rule 1. The current end must first be tried against the existing starts, and only then take its own place in the queue as a start.
  • Returning 0 when nothing is found. This problem asks for -1.

Original problem: LeetCode 862: Shortest Subarray with Sum at Least K