Shortest Subarray with Sum at Least K

Hard
805.

Shortest Subarray with Sum at Least K

Shortest Subarray with Sum at Least K is a hard coding problem on arrays, binary search and prefix sum, asked in Amazon, Google and Microsoft interviews.

Return the length of the shortest non-empty subarray of nums whose sum is at least k, or 0 if there is none.

(Negative values are allowed, which is what makes this harder than the all-positive version.)

Example 1

Input
nums = [1], k = 1
Output
1

Example 2

Input
nums = [1,2], k = 4
Output
0
Explanation
The whole array only sums to 3.

Example 3

Input
nums = [2,-1,2], k = 3
Output
3
Explanation
The -1 forces the window to span everything.

Constraints

  • 1 <= nums.length <= 100000
  • -100000 <= nums[i] <= 100000
  • 1 <= k <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Subarray with Sum at Least K — Problem & Solution

Shortest Subarray with Sum at Least K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Shortest Subarray with Sum at Least K is a hard coding problem on arrays, binary search and prefix sum, asked in Amazon, Google and Microsoft interviews.

Problem statement

Return the length of the shortest non-empty subarray of nums whose sum is at least k, or 0 if there is none.

(Negative values are allowed, which is what makes this harder than the all-positive version.)

Example 1

Input: nums = [1], k = 1
Output: 1

Example 2

Input: nums = [1,2], k = 4
Output: 0
Explanation: The whole array only sums to 3.

Example 3

Input: nums = [2,-1,2], k = 3
Output: 3
Explanation: The -1 forces the window to span everything.

Constraints

  • 1 <= nums.length <= 100000
  • -100000 <= nums[i] <= 100000
  • 1 <= k <= 1000000000

Hints for Shortest Subarray with Sum at Least K

  1. Hint 1

    With negative values a plain two-pointer window fails — extending a window can lower its sum.

  2. Hint 2

    Work with prefix sums: you need indices i < j with pre[j] - pre[i] >= k and j - i minimal.

  3. Hint 3

    Keep the candidate i values in a deque that stays strictly increasing in prefix sum.

How to solve Shortest Subarray with Sum at Least K

Reduce to prefix sums and keep a monotonic deque of candidate left endpoints. Two rules prune it: a candidate already satisfied can be retired (nothing later will beat it), and a candidate with a prefix sum at least as large as a newer one is useless.

Approach

  1. Build pre[0…n] with pre[i+1] = pre[i] + nums[i].
  2. For each i, while pre[i] - pre[dq.front()] >= k, record i - dq.front() and pop the front.
  3. While pre[dq.back()] >= pre[i], pop the back — a later index with a smaller prefix sum dominates.
  4. Push i. Return the best length, or 0 if none was found.

Why it works

Popping the front is safe because any later right end paired with that index gives a longer subarray, and it is already satisfied. Popping the back is safe because a smaller prefix sum at a larger index is better on both counts: it yields a bigger difference and a shorter span. The deque therefore stays increasing in prefix sum, and each index is pushed and popped once.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • A sliding window without the deque is wrong here — negative numbers break the monotonicity.
  • Prefix sums reach 10^5 · 10^5 = 10^10, so they need 64-bit.
  • The answer for 'no such subarray' is 0, not -1.

Reference solution

Python

from collections import deque
from typing import List

def shortestSubarray(nums: List[int], k: int) -> int:
    n = len(nums)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + nums[i]
    dq = deque()
    best = n + 1
    for i in range(n + 1):
        while dq and pre[i] - pre[dq[0]] >= k:
            best = min(best, i - dq.popleft())
        while dq and pre[dq[-1]] >= pre[i]:
            dq.pop()
        dq.append(i)
    return best if best <= n else 0

Java

public static int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
    int[] dq = new int[n + 1];
    int head = 0, tail = 0, best = n + 1;
    for (int i = 0; i <= n; i++) {
        while (tail > head && pre[i] - pre[dq[head]] >= k) {
            best = Math.min(best, i - dq[head]);
            head++;
        }
        while (tail > head && pre[dq[tail - 1]] >= pre[i]) tail--;
        dq[tail++] = i;
    }
    return best <= n ? best : 0;
}

C++

int shortestSubarray(vector<int>& nums, int k) {
    int n = (int) nums.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
    deque<int> dq;
    int best = n + 1;
    for (int i = 0; i <= n; i++) {
        while (!dq.empty() && pre[i] - pre[dq.front()] >= k) {
            best = min(best, i - dq.front());
            dq.pop_front();
        }
        while (!dq.empty() && pre[dq.back()] >= pre[i]) dq.pop_back();
        dq.push_back(i);
    }
    return best <= n ? best : 0;
}

JavaScript

var shortestSubarray = function(nums, k) {
    var n = nums.length;
    var pre = [0];
    for (var i = 0; i < n; i++) pre.push(pre[i] + nums[i]);
    var dq = [];
    var head = 0;
    var best = n + 1;
    for (var j = 0; j <= n; j++) {
        while (dq.length > head && pre[j] - pre[dq[head]] >= k) {
            var len = j - dq[head];
            head++;
            if (len < best) best = len;
        }
        while (dq.length > head && pre[dq[dq.length - 1]] >= pre[j]) dq.pop();
        dq.push(j);
    }
    return best <= n ? best : 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search