Shortest Subarray with Sum at Least K solution and explanation
Google
9 more videos on this problem
Shortest Subarray with Sum at Least K | Leetcode 862Techdose · 21:31 · 43K views
Shortest Subarray with Sum at Least K - Leetcode 862 - PythonNeetCodeIO · 27:57 · 27K views
Shortest Subarray with Sum at Least K | Already Studied Concept | Leetcode 862 | codestorywithMIKcodestorywithMIK · 35:37 · 21K views
862. Shortest Subarray with Sum at Least K | 4 Approaches | Min Heap | Monotonic DequeAryan Mittal · 30:39 · 7K views
LeetCode 862. Shortest Subarray with Sum at Least K (2nd time)Happy Coding · 23:37 · 5K views
LeetCode 862. Shortest Subarray with Sum at Least KHappy Coding · 31:26 · 5K views
Shortest Subarray with Sum at Least K | O(N) solution | Leetcode - 862Algorithms Made Easy · 35:17 · 4K views
Leetcode 862. Shortest Subarray with Sum at Least KAlgorithms for Big Bucks · 14:29 · 1K views
LeetCode 862 Shortest Subarray with Sum at Least K | Sliding Window | Heap | Hard | MetaCode Harmony · 25:44 · 1K views
[LEETCODE HARD] 862. Shortest Subarray with Sum at Least K | Daily Challenge | 17 Nov 2024 | POTDCTO Bhaiya · 23:27 · 512 views
The problem
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1], k = 1 Output: 1
Example 2:
Input: nums = [1,2], k = 4 Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3 Output: 3
Constraints:
1 <= nums.length <= 105-105 <= nums[i] <= 1051 <= k <= 109
Approach overview
Problem Overview: You are given an integer array nums and an integer k. The goal is to find the length of the shortest non‑empty subarray whose sum is at least k. The challenge comes from negative numbers in the array, which break the standard sliding window strategy used for positive-only arrays.
Approach 1: Brute Force Subarray Check (O(n²) time, O(1) space)
The most direct strategy is to examine every possible subarray. Start from each index i, keep a running sum while extending the subarray to the right, and stop once the sum becomes at least k. Track the minimum length encountered. This works because every subarray is evaluated explicitly, but the nested iteration leads to O(n²) time in the worst case. It is useful as a baseline to verify correctness and understand the structure of the problem, but it does not scale when n is large.
Approach 2: Prefix Sum + Monotonic Deque (O(n) time, O(n) space)
The optimal approach uses prefix sums and a monotonic queue. First compute a prefix array where prefix[i] stores the sum of the first i elements. Any subarray sum from i to j can then be computed as prefix[j] - prefix[i]. The goal becomes finding indices i < j where this difference is at least k while minimizing j - i.
A deque stores candidate prefix indices in increasing order of their prefix values. While iterating through the prefix array, two checks keep the structure optimal. First, if the difference between the current prefix and the front of the deque is at least k, you found a valid subarray and update the minimum length while popping from the front. Second, maintain monotonicity: if the current prefix value is smaller than the last stored prefix, remove the larger one because it will never produce a better result later. Each index enters and leaves the deque at most once, which keeps the total runtime linear.
This technique handles negative numbers gracefully and avoids the pitfalls of a standard sliding window. The combination of prefix sums and a monotonic structure ensures that only useful candidates remain in the deque during iteration.
Recommended for interviews: The prefix sum with monotonic deque solution is what interviewers expect for this problem. It demonstrates understanding of prefix transformations and efficient candidate pruning using a deque. Mentioning the brute force approach first shows you understand the search space, but implementing the O(n) solution signals strong algorithmic maturity.
Approach 1: Prefix Sum and Sliding Window with Deque
This approach uses a prefix sum array to store cumulative sums and a deque to maintain the indices of suffix values. The deque is used to efficiently find the shortest subarray with the required sum condition. For each element, we calculate the prefix sum and determine the shortest subarray that satisfies the condition using the deque.
from collections import deque
def shortest_subarray(nums, k):
n = len(nums)
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + nums[i]
dq = deque()
result = float('inf')
for i in range(n + 1):
while dq and prefix_sum[i] - prefix_sum[dq[0]] >= k:
result = min(result, i - dq.popleft())
while dq and prefix_sum[i] <= prefix_sum[dq[-1]]:
dq.pop()
dq.append(i)
return result if result != float('inf') else -1
nums = [2, -1, 2]
k = 3
print(shortest_subarray(nums, k)) # Output: 3import java.util.Deque;
import java.util.LinkedList;
public class ShortestSubarraySum {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] prefixSum = new long[n + 1];
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
Deque<Integer> dq = new LinkedList<>();
int result = Integer.MAX_VALUE;
for (int i = 0; i <= n; ++i) {
while (!dq.isEmpty() && prefixSum[i] - prefixSum[dq.peekFirst()] >= k) {
result = Math.min(result, i - dq.pollFirst());
}
while (!dq.isEmpty() && prefixSum[i] <= prefixSum[dq.peekLast()])
dq.pollLast();
dq.addLast(i);
}
return result == Integer.MAX_VALUE ? -1 : result;
}
public static void main(String[] args) {
ShortestSubarraySum solver = new ShortestSubarraySum();
int[] nums = {2, -1, 2};
int k = 3;
System.out.println(solver.shortestSubarray(nums, k)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <deque>
#include <limits>
using namespace std;
int shortestSubarray(vector<int>& nums, int k) {
deque<int> dq;
int n = nums.size();
vector<long> prefixSum(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int result = INT_MAX;
for (int i = 0; i <= n; ++i) {
while (!dq.empty() && prefixSum[i] - prefixSum[dq.front()] >= k) {
result = min(result, i - dq.front());
dq.pop_front();
}
while (!dq.empty() && prefixSum[i] <= prefixSum[dq.back()])
dq.pop_back();
dq.push_back(i);
}
return result == INT_MAX ? -1 : result;
}
int main() {
vector<int> nums = {2, -1, 2};
int k = 3;
cout << shortestSubarray(nums, k) << endl; // Output: 3
return 0;
}function shortestSubarray(nums, k) {
let n = nums.length;
let prefixSum = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
let deque = [];
let result = Infinity;
for (let i = 0; i <= n; ++i) {
while (deque.length > 0 && prefixSum[i] - prefixSum[deque[0]] >= k) {
result = Math.min(result, i - deque.shift());
}
while (deque.length > 0 && prefixSum[i] <= prefixSum[deque[deque.length - 1]])
deque.pop();
deque.push(i);
}
return result === Infinity ? -1 : result;
}
let nums = [2, -1, 2];
let k = 3;
console.log(shortestSubarray(nums, k)); // Output: 3#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
int shortestSubarray(int* nums, int numsSize, int k) {
int* prefixSum = (int*) malloc((numsSize + 1) * sizeof(int));
prefixSum[0] = 0;
for (int i = 0; i < numsSize; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int deque[numsSize + 1];
int front = 0, back = 0;
int result = INT_MAX;
for (int i = 0; i <= numsSize; ++i) {
while (front < back && prefixSum[i] - prefixSum[deque[front]] >= k) {
if (result > i - deque[front])
result = i - deque[front];
front++;
}
while (front < back && prefixSum[i] <= prefixSum[deque[back - 1]])
back--;
deque[back++] = i;
}
free(prefixSum);
return result == INT_MAX ? -1 : result;
}
int main() {
int nums[] = {2, -1, 2};
int k = 3;
int result = shortestSubarray(nums, 3, k);
printf("%d\n", result); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int ShortestSubarray(int[] nums, int k) {
int n = nums.Length;
long[] prefixSum = new long[n + 1];
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
LinkedList<int> deque = new LinkedList<int>();
int result = int.MaxValue;
for (int i = 0; i <= n; ++i) {
while (deque.Count > 0 && prefixSum[i] - prefixSum[deque.First.Value] >= k) {
result = Math.Min(result, i - deque.First.Value);
deque.RemoveFirst();
}
while (deque.Count > 0 && prefixSum[i] <= prefixSum[deque.Last.Value])
deque.RemoveLast();
deque.AddLast(i);
}
return result == int.MaxValue ? -1 : result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {2, -1, 2};
int k = 3;
Console.WriteLine(sol.ShortestSubarray(nums, k)); // Output: 3
}
}This Python implementation uses a deque to hold indices of prefix sums. As it iterates through the prefix sums, it checks whether removing the earliest index in the deque helps in achieving a valid subarray that sums to at least k. When it finds such an index, it calculates and potentially updates the shortest length of this subarray.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the prefix sum list and deque.
Approach 2: Brute Force Approach
Although a brute force approach will not be efficient for larger inputs, it's a good starting point to understand the combination of elements in this problem. We iterate over every starting point in the array and extend the subarray until the sum requirement is satisfied or the end of the array is reached. This ensures that we verify all possible subarray combinations.
def shortest_subarray(nums, k):
minLength = float('inf')
for start in range(len(nums)):
sum_so_far = 0
for end in range(start, len(nums)):
sum_so_far += nums[end]
if sum_so_far >= k:
minLength = min(minLength, end - start + 1)
break
return minLength if minLength != float('inf') else -1
nums = [2, -1, 2]
k = 3
print(shortest_subarray(nums, k)) # Output: 3public class ShortestSubarrayBruteForce {
public int shortestSubarray(int[] nums, int k) {
int minLength = Integer.MAX_VALUE;
for (int start = 0; start < nums.length; ++start) {
int sum = 0;
for (int end = start; end < nums.length; ++end) {
sum += nums[end];
if (sum >= k) {
minLength = Math.min(minLength, end - start + 1);
break;
}
}
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
public static void main(String[] args) {
ShortestSubarrayBruteForce solver = new ShortestSubarrayBruteForce();
int[] nums = {2, -1, 2};
int k = 3;
System.out.println(solver.shortestSubarray(nums, k)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int shortestSubarray(vector<int>& nums, int k) {
int minLength = INT_MAX;
for (int start = 0; start < nums.size(); ++start) {
int sum = 0;
for (int end = start; end < nums.size(); ++end) {
sum += nums[end];
if (sum >= k) {
minLength = min(minLength, end - start + 1);
break;
}
}
}
return minLength == INT_MAX ? -1 : minLength;
}
int main() {
vector<int> nums = {2, -1, 2};
int k = 3;
cout << shortestSubarray(nums, k) << endl; // Output: 3
return 0;
}function shortestSubarray(nums, k) {
let minLength = Infinity;
for (let start = 0; start < nums.length; ++start) {
let sum = 0;
for (let end = start; end < nums.length; ++end) {
sum += nums[end];
if (sum >= k) {
minLength = Math.min(minLength, end - start + 1);
break;
}
}
}
return minLength === Infinity ? -1 : minLength;
}
let nums = [2, -1, 2];
let k = 3;
console.log(shortestSubarray(nums, k)); // Output: 3#include <stdio.h>
#include <limits.h>
int shortestSubarray(int* nums, int numsSize, int k) {
int minLength = INT_MAX;
for (int start = 0; start < numsSize; ++start) {
int sum = 0;
for (int end = start; end < numsSize; ++end) {
sum += nums[end];
if (sum >= k) {
minLength = (end - start + 1) < minLength ? (end - start + 1) : minLength;
break;
}
}
}
return minLength == INT_MAX ? -1 : minLength;
}
int main() {
int nums[] = {2, -1, 2};
int k = 3;
int result = shortestSubarray(nums, 3, k);
printf("%d\n", result); // Output: 3
return 0;
}using System;
public class ShortestSubarrayBruteForce {
public int ShortestSubarray(int[] nums, int k) {
int minLength = int.MaxValue;
for (int start = 0; start < nums.Length; ++start) {
int sum = 0;
for (int end = start; end < nums.Length; ++end) {
sum += nums[end];
if (sum >= k) {
minLength = Math.Min(minLength, end - start + 1);
break;
}
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
public static void Main(string[] args) {
ShortestSubarrayBruteForce sol = new ShortestSubarrayBruteForce();
int[] nums = {2, -1, 2};
int k = 3;
Console.WriteLine(sol.ShortestSubarray(nums, k)); // Output: 3
}
}The Python solution takes a basic implementation to demonstrate the fundamental idea of subarray examination. It iteratively reviews each potential subarray while accumulating the sum, ceasing further calculations when the subarray satisfies the sum constraint k and noting minimal lengths.
Time Complexity: O(n^2), since the method extends the examination to all subarray possibilities.
Space Complexity: O(1), given its additional space-free approach.
Approach 3: Default Approach
function shortestSubarray(nums: number[], k: number): number {
const [n, MAX] = [nums.length, Number.POSITIVE_INFINITY];
const s = Array(n + 1).fill(0);
const q: number[] = [];
let ans = MAX;
for (let i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
for (let i = 0; i < n + 1; i++) {
while (q.length && s[i] - s[q[0]] >= k) {
ans = Math.min(ans, i - q.shift()!);
}
while (q.length && s[i] <= s[q.at(-1)!]) {
q.pop();
}
q.push(i);
}
return ans === MAX ? -1 : ans;
}func shortestSubarray(nums []int, k int) int {
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
q := []int{}
ans := n + 1
for i, v := range s {
for len(q) > 0 && v-s[q[0]] >= k {
ans = min(ans, i-q[0])
q = q[1:]
}
for len(q) > 0 && s[q[len(q)-1]] >= v {
q = q[:len(q)-1]
}
q = append(q, i)
}
if ans > n {
return -1
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum and Sliding Window with Deque | Time Complexity: O(n), where n is the length of the array. |
| Brute Force Approach | Time Complexity: O(n^2), since the method extends the examination to all subarray possibilities. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n²) | O(1) | Good for understanding the problem or very small input sizes |
| Prefix Sum + Monotonic Deque | O(n) | O(n) | General optimal solution, works even with negative numbers |
Frequently asked questions
Is Shortest Subarray with Sum at Least K easy or hard?
The problem is classified as Hard because negative numbers invalidate the standard sliding window technique. Solving it efficiently requires recognizing the prefix sum transformation and maintaining a monotonic deque to keep candidate starting points optimal.
Shortest Subarray with Sum at Least K Python/Java solution
Most implementations follow the same pattern: compute prefix sums, maintain a deque of candidate indices, and update the shortest length whenever the current prefix minus the front prefix is at least K. The algorithm translates directly to Python, Java, C++, or JavaScript with O(n) time complexity.
How to solve Shortest Subarray with Sum at Least K in O(n)?
Compute prefix sums so any subarray sum becomes prefix[j] - prefix[i]. Maintain a deque of indices with increasing prefix values. While iterating, remove indices from the front if the difference with the current prefix is at least K, and remove larger prefix values from the back to preserve monotonic order. This guarantees a linear scan.
What is the best approach for Shortest Subarray with Sum at Least K?
The best approach uses prefix sums combined with a monotonic deque. Prefix sums allow constant-time subarray sum queries, while the deque keeps candidate indices in increasing prefix order. This structure ensures each index is processed at most once, resulting in O(n) time complexity and O(n) space.
Is Shortest Subarray with Sum at Least K asked at Google/Amazon/Meta?
This problem pattern appears in interviews at companies like Google, Amazon, and Meta because it combines prefix sums, monotonic queues, and subarray optimization. Interviewers often use it to evaluate whether candidates can optimize beyond brute force and reason about prefix-based transformations.
What data structure is used in Shortest Subarray with Sum at Least K?
The key data structure is a deque used as a monotonic queue. It stores indices of the prefix sum array while maintaining increasing prefix values. This allows efficient removal of useless candidates and fast detection of valid subarrays.
What is the time complexity of Shortest Subarray with Sum at Least K?
The optimal solution runs in O(n) time using a prefix sum array and a monotonic deque. Each index is added and removed from the deque at most once. A naive brute force approach checks every subarray and takes O(n²) time.