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 <= 109Problem 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.
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.
The program calculates the prefix sum array and uses a deque to manage the indices of potential subarray starts. It iterates over each prefix sum. For each prefix sum, it checks if there's any prior prefix sum that's at least k less than the current sum. If so, it updates the potential minimum length of the subarray. After finishing the loop, if result is still INT_MAX, it returns -1 as no valid subarray exists.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), for the prefix sum array and deque.
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.
This solution checks each subarray starting from every index. We accumulate the sum as we extend the subarray, and once we reach a sum that's at least k, we update our minimum length if this subarray is shorter than previously found subarrays. It's computationally intense and feasible only for small arrays.
Time Complexity: O(n^2), where n is the length of the array.
Space Complexity: O(1), since we're not using additional data structures.
Python
Java
C++
Go
TypeScript
JavaScript
| 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), where n is the length of the array. |
| Default Approach | — |
| 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 |
Shortest Subarray with Sum at Least K | Leetcode 862 • Techdose • 42,659 views views
Watch 9 more video solutions →Practice Shortest Subarray with Sum at Least K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor