Shortest Subarray with Sum at Least K

HardProblemExternal linkUpdated Oct 31, 2026

Description

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray whose sum is at least k. If no subarray reaches k, return -1.

A subarray is a contiguous part of the array. The values may be negative.

Examples

Example 1

Input: nums = [1], k = 1

Output: 1

Explanation: The single value reaches 1 on its own.

Example 2

Input: nums = [1, 2], k = 4

Output: -1

Explanation: The whole array sums to 3, short of 4, so no subarray works: −1.

Example 3

Input: nums = [2, -1, 2], k = 3

Output: 3

Explanation: Only the whole array reaches 3.

Example 4

Input: nums = [84, -37, 32, 40, 95], k = 167

Output: 3

Explanation: 32 + 40 + 95 = 167. A window that shrinks from the left stops at 84, because dropping 84 makes the sum fall short, and never gets past the −37.

Constraints

1 ≤ nums.length ≤ 10^5
−10^5 ≤ nums[i] ≤ 10^5
1 ≤ k ≤ 10^9

Editorial

Brute Force

Intuition

With prefix sums, prefix[j] is the sum of the first j values, and the subarray from index i up to index j - 1 sums to prefix[j] - prefix[i]. So try every start i: walk the end j to the right, and the first j whose sum reaches k is the shortest subarray from that start. The best over all starts is the answer.

Step-by-Step Explanation

Let's trace nums = [84, -37, 32, 40, 95], k = 167:

From index 0, the sum first reaches 167 at index 4 (84, −37, 32, 40 and 95), length 5.
From index 1, no end reaches 167; the whole rest sums to 130.
From index 2, the sum first reaches 167 at index 4 (32, 40 and 95), length 3.
From index 3, no end reaches 167; the whole rest sums to 135.
From index 4, no end reaches 167; the whole rest sums to 95.

Every Start, the First End That Reaches k — The outlined window is the shortest subarray from each start.

Algorithm

Build prefix, with prefix[0] = 0.
For each start i, for each end j > i: if prefix[j] - prefix[i] >= k, record j - i and stop.
Return the shortest length recorded, or −1.

Code

The prefix sums can reach 10^10, so C++ and Java keep them in 64 bits.

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefix(n + 1, 0);  // prefix[j]: the sum of the first j values
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        int best = n + 1;
        for (int i = 0; i < n; i++)          // every start
            for (int j = i + 1; j <= n; j++)
                if (prefix[j] - prefix[i] >= k) {   // the first end that reaches k is this start's shortest
                    best = min(best, j - i);
                    break;
                }
        return best <= n ? best : -1;
    }
};

class Solution:
    def shortestSubarray(self, nums: list[int], k: int) -> int:
        prefix = [0]                         # prefix[j]: the sum of the first j values
        for x in nums:
            prefix.append(prefix[-1] + x)
        best = len(nums) + 1
        for i in range(len(nums)):           # every start
            for j in range(i + 1, len(nums) + 1):
                if prefix[j] - prefix[i] >= k:   # the first end that reaches k is this start's shortest
                    best = min(best, j - i)
                    break
        return best if best <= len(nums) else -1

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];          // prefix[j]: the sum of the first j values
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        int best = n + 1;
        for (int i = 0; i < n; i++)               // every start
            for (int j = i + 1; j <= n; j++)
                if (prefix[j] - prefix[i] >= k) { // the first end that reaches k is this start's shortest
                    best = Math.min(best, j - i);
                    break;
                }
        return best <= n ? best : -1;
    }
}

var shortestSubarray = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);  // prefix[j]: the sum of the first j values
    for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    let best = n + 1;
    for (let i = 0; i < n; i++)              // every start
        for (let j = i + 1; j <= n; j++)
            if (prefix[j] - prefix[i] >= k) {   // the first end that reaches k is this start's shortest
                best = Math.min(best, j - i);
                break;
            }
    return best <= n ? best : -1;
};

Complexity Analysis

Time Complexity: O(n²)

When no subarray reaches k, every pair of start and end is tried.

Space Complexity: O(n)

The prefix sums.

Why This Approach Is Not Efficient

With 10^5 values and no subarray reaching k, that's 5 × 10^9 pairs, over the time limit in Python and JavaScript.

The usual fix for "shortest subarray with a sum" is a two-pointer window: grow the right edge, and while the sum reaches k, record it and shrink from the left. That's right when every value is positive, because shrinking can only lower the sum. Here it isn't: on Example 4 the window starts at 84, and once 84 leaves, the sum falls short, so the window stops shrinking and never drops the −37 behind it. It answers 5 instead of 3.

Stay with prefix sums and ask which starts are worth keeping. For an end j we want the latest start i with prefix[i] <= prefix[j] - k. A start that has been used can go (later ends from it are only longer), and a start with a later, lower prefix after it can go too (the later one is better for every end). What's left is a deque of starts whose prefix sums rise.

Optimal Approach - Prefix Sums and a Monotonic Deque

Intuition

Walk j over the prefix sums, keeping a deque of start indexes whose prefix sums rise from front to back:

From the front: while prefix[j] - prefix[front] >= k, record j - front and pop the front. Any later end from that start would be longer, so it's done. Several starts can finish at the same j, so this is a while.
From the back: while prefix[j] <= prefix[back], pop the back. Start j is later and no higher, so it beats that start for every end still to come.
Then push j as a start.

Step-by-Step Explanation

Let's trace nums = [84, -37, 32, 40, 95], k = 167, whose prefix sums are 0, 84, 47, 79, 119 and 214:

Start 0 joins the deque.
84 − 0 falls short of 167. Start 1 joins the deque.
47 − 0 falls short of 167. 47 is no higher than the 84 of start 1, and start 2 is later, so start 2 beats start 1 for every end to come; start 1 is knocked out. Start 2 joins the deque.
79 − 0 falls short of 167. Start 3 joins the deque.
119 − 0 falls short of 167. Start 4 joins the deque.
214 − 0 reaches 167, so from start 0 there's a subarray of length 5; later ends from that start are only longer, so it's done. 214 − 47 reaches 167, so from start 2 there's a subarray of length 3; later ends from that start are only longer, so it's done. Start 5 joins the deque.

Prefix Sums and the Best Start — Green starts are used up; the deque below holds the starts still worth keeping.

Algorithm

Build prefix, with prefix[0] = 0. Start with an empty deque and best = n + 1.
For each j from 0 to n: while the deque isn't empty and prefix[j] - prefix[front] >= k, set best = min(best, j - front) and pop the front. Then pop the back while prefix[j] <= prefix[back]. Push j.
Return best, or −1 if it's still n + 1.

Code

The prefix sums can reach 10^10, so C++ and Java keep them in 64 bits. JavaScript keeps the deque in an array with a head and a tail index.

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefix(n + 1, 0);  // prefix[j]: the sum of the first j values
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        deque<int> dq;                       // start indexes, their prefix sums rising
        int best = n + 1;
        for (int j = 0; j <= n; j++) {
            while (!dq.empty() && prefix[j] - prefix[dq.front()] >= k) {
                best = min(best, j - dq.front());   // the shortest from this start: later ends are longer
                dq.pop_front();
            }
            while (!dq.empty() && prefix[j] <= prefix[dq.back()])
                dq.pop_back();               // j is later and no higher: a better start for every end
            dq.push_back(j);
        }
        return best <= n ? best : -1;
    }
};

from collections import deque

class Solution:
    def shortestSubarray(self, nums: list[int], k: int) -> int:
        prefix = [0]                         # prefix[j]: the sum of the first j values
        for x in nums:
            prefix.append(prefix[-1] + x)
        dq = deque()                         # start indexes, their prefix sums rising
        best = len(nums) + 1
        for j, p in enumerate(prefix):
            while dq and p - prefix[dq[0]] >= k:
                best = min(best, j - dq.popleft())   # the shortest from this start: later ends are longer
            while dq and p <= prefix[dq[-1]]:
                dq.pop()                     # j is later and no higher: a better start for every end
            dq.append(j)
        return best if best <= len(nums) else -1

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];          // prefix[j]: the sum of the first j values
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        Deque<Integer> dq = new ArrayDeque<>();   // start indexes, their prefix sums rising
        int best = n + 1;
        for (int j = 0; j <= n; j++) {
            while (!dq.isEmpty() && prefix[j] - prefix[dq.peekFirst()] >= k)
                best = Math.min(best, j - dq.pollFirst());   // the shortest from this start: later ends are longer
            while (!dq.isEmpty() && prefix[j] <= prefix[dq.peekLast()])
                dq.pollLast();                    // j is later and no higher: a better start for every end
            dq.offerLast(j);
        }
        return best <= n ? best : -1;
    }
}

var shortestSubarray = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);  // prefix[j]: the sum of the first j values
    for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    const dq = new Int32Array(n + 1);    // start indexes, their prefix sums rising: dq[head .. tail - 1]
    let head = 0, tail = 0, best = n + 1;
    for (let j = 0; j <= n; j++) {
        while (tail > head && prefix[j] - prefix[dq[head]] >= k)
            best = Math.min(best, j - dq[head++]);   // the shortest from this start: later ends are longer
        while (tail > head && prefix[j] <= prefix[dq[tail - 1]])
            tail--;                      // j is later and no higher: a better start for every end
        dq[tail++] = j;
    }
    return best <= n ? best : -1;
};

Complexity Analysis

Time Complexity: O(n)

Each prefix index is pushed once and popped at most once, from one end or the other.

Space Complexity: O(n)

The prefix sums and the deque.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Shrinking a two-pointer window. while total >= k:

On nums = [84, -37, 32, 40, 95], k = 167 it returns 5; the answer is 3. Growing the right edge and shrinking from the left while the sum is at least k is right only when every value is positive. With a negative after the left edge, dropping the left value can make the sum fall short, and the window stops before it ever drops the negative that comes next.

Finishing one start per end. if dq and p - prefix[dq[0]] >= k:

On nums = [84, -37, 32, 40, 95], k = 167 it returns 5; the answer is 3. One end can finish several starts at once, the earliest first. An if records only the earliest, the longest of them, and never tries the later starts that give shorter subarrays. Use a while.

Leaving out the empty prefix. prefix, total = [], 0

On nums = [3, -1], k = 3 it returns -1; the answer is 1. A subarray from index 0 to j sums to prefix[j] - prefix[0], and that needs prefix[0] = 0, the sum of no values, as a start. Without it, no subarray can start at index 0.

Where This Pattern Is Taught

This problem practises prefix sums with a monotonic deque. It's taught in Monotonic Deque: the Window's Maximum, which steps through this example and shows the two-pointer window failing on it.