Shortest Subarray with Sum at Least K

Hard

#0816Time: O(n^2), where n is the number of elements in `nums`. The prefix sum calculation takes O(n), but the nested loops to check every subarray dominate the runtime.Space: O(n) to store the prefix sum array.

Patterns

Sliding Window Prefix Sum

Algorithms

Binary Search

Data structures

Array Heap (Priority Queue)Queue Monotonic Queue

Prompt

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but inefficient approach involves pre-calculating prefix sums to quickly find the sum of any subarray. We then iterate through all possible start and end points of a subarray, check if its sum is at least k, and keep track of the minimum length found.

Algorithm

Create a prefix sum array prefix of size n + 1. Use long to prevent integer overflow, as sums can be large.
Populate the prefix array: prefix[i+1] = prefix[i] + nums[i] for i from 0 to n-1.
Initialize minLength = n + 1 to store the result.
Iterate with a start index i from 0 to n-1.
Inside this loop, iterate with an end index j from i to n-1.
Calculate the subarray sum: sum = prefix[j+1] - prefix[i].
If sum >= k, update minLength = Math.min(minLength, j - i + 1).
After the loops, if minLength is still n + 1, return -1. Otherwise, return minLength.

Walkthrough

This method improves upon a naive brute-force solution by optimizing the sum calculation for each subarray.

Prefix Sum Calculation: First, we create a prefix sum array, prefix, of size n + 1, where n is the length of nums. prefix[i] stores the sum of elements from nums[0] to nums[i-1]. prefix[0] is initialized to 0. This allows us to calculate the sum of any subarray nums[i...j] in constant time using the formula prefix[j+1] - prefix[i]. This pre-computation step takes O(n) time.
Iterating Subarrays: After computing the prefix sums, we use two nested loops to examine every possible non-empty subarray. The outer loop selects a starting index i from 0 to n-1, and the inner loop selects an ending index j from i to n-1.
Checking Condition: For each subarray defined by (i, j), we calculate its sum prefix[j+1] - prefix[i]. If this sum is greater than or equal to k, we have found a valid subarray. We then update our minimum length found so far with min(minLength, j - i + 1).
Result: We initialize minLength to a value larger than n (e.g., n + 1). If minLength remains this value after checking all subarrays, it means no solution exists, and we return -1. Otherwise, we return the final minLength.

1class Solution {2    public int shortestSubarray(int[] nums, int k) {3        int n = nums.length;4        long[] prefix = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefix[i + 1] = prefix[i] + nums[i];7        }8 9        int minLength = n + 1;10        for (int i = 0; i < n; i++) {11            for (int j = i; j < n; j++) {12                long sum = prefix[j + 1] - prefix[i];13                if (sum >= k) {14                    minLength = Math.min(minLength, j - i + 1);15                }16            }17        }18 19        return minLength == n + 1 ? -1 : minLength;20    }21}

Complexity

Time

O(n^2), where n is the number of elements in `nums`. The prefix sum calculation takes O(n), but the nested loops to check every subarray dominate the runtime.

Space

O(n) to store the prefix sum array.

Trade-offs

Pros

More efficient than a naive O(n^3) brute-force approach.
Relatively easy to understand the logic based on prefix sums.

Cons

The O(n^2) time complexity is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error.

The optimal solution uses prefix sums combined with a sliding window managed by a monotonic deque. This approach achieves linear time complexity by efficiently finding the shortest valid subarray ending at each position. The deque helps maintain potential starting points for subarrays in a way that handles the complication of negative numbers.

Algorithm

Create a long prefix sum array prefix of size n + 1 and populate it.
Initialize minLength = n + 1 and an empty Deque<Integer> dq.
Iterate with index y from 0 to n (representing the end of the subarray).
Check for valid subarrays: While the deque is not empty and prefix[y] - prefix[dq.peekFirst()] >= k, update minLength = min(minLength, y - dq.pollFirst()) and remove the first element from the deque.
Maintain deque monotonicity: While the deque is not empty and prefix[y] <= prefix[dq.peekLast()], remove the last element from the deque.
Add the current index y to the end of the deque.
After the loop, if minLength > n, return -1. Otherwise, return minLength.

Walkthrough

This advanced approach leverages prefix sums to reframe the problem and a deque to maintain candidate indices efficiently.

The problem is to find the smallest y - x such that sum(nums[x...y-1]) >= k. Using prefix sums P, this is equivalent to finding the smallest y - x such that P[y] - P[x] >= k.

For a fixed endpoint y, we want to find an x < y that satisfies P[x] <= P[y] - k and is as large as possible (to minimize y - x).

We can process the prefix sums P from left to right (indexed by y). We use a deque to store indices x of promising starting points. The deque will store indices d_1, d_2, ... such that their corresponding prefix sums are strictly increasing: P[d_1] < P[d_2] < ....

Algorithm Steps:

Prefix Sums: Compute the prefix sum array P of size n+1. Use long to avoid overflow.
Initialization: Create an empty deque dq to store indices and initialize minLength = n + 1.
Iteration: Iterate through the prefix sum array with index y from 0 to n. a. Condition Check (Shrinking Window from Left): Look at the index at the front of the deque, x = dq.peekFirst(). If P[y] - P[x] >= k, we've found a valid subarray of length y - x. We update minLength and then remove x from the deque (dq.pollFirst()). We remove it because for any future endpoint y' > y, a subarray starting at x would be longer than y' - x', where x' is another valid start. We've found the shortest possible subarray starting at x, so it's no longer needed. b. Monotonicity Maintenance (Optimizing Candidates): Look at the index at the back of the deque, x_last = dq.peekLast(). If P[y] <= P[x_last], we remove x_last from the deque (dq.pollLast()). The reason is that y is a better future candidate for a starting index than x_last. If we have x_last < y and P[x_last] >= P[y], then for any future endpoint z > y, if P[z] - P[x_last] >= k, it must be that P[z] - P[y] >= k as well. The subarray starting at y (z-y) would be shorter than the one starting at x_last (z-x_last). So, x_last becomes redundant. c. Add to Window: Add the current index y to the back of the deque.

After iterating through all y, if minLength is still n + 1, no such subarray exists. Otherwise, minLength holds the answer.

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public int shortestSubarray(int[] nums, int k) {6        int n = nums.length;7        long[] prefix = new long[n + 1];8        for (int i = 0; i < n; i++) {9            prefix[i + 1] = prefix[i] + nums[i];10        }11 12        int minLength = n + 1;13        Deque<Integer> dq = new ArrayDeque<>();14 15        for (int y = 0; y <= n; y++) {16            // Condition: prefix[y] - prefix[x] >= k17            while (!dq.isEmpty() && prefix[y] - prefix[dq.peekFirst()] >= k) {18                minLength = Math.min(minLength, y - dq.pollFirst());19            }20 21            // Maintain monotonic deque: prefix[d1] < prefix[d2] < ...22            while (!dq.isEmpty() && prefix[y] <= prefix[dq.peekLast()]) {23                dq.pollLast();24            }25 26            dq.addLast(y);27        }28 29        return minLength == n + 1 ? -1 : minLength;30    }31}

Complexity

Time

O(n), where n is the length of `nums`. Each index is added to and removed from the deque at most once. The entire process is a single pass over the prefix sum array.

Space

O(n) for storing the prefix sum array and the deque. In the worst-case scenario, the deque could potentially store all `n+1` indices.

Trade-offs

Pros

Optimal O(n) time complexity, making it very efficient for large inputs.
Correctly handles arrays with negative numbers, which is a key challenge in this problem.

Cons

The logic is more complex and less intuitive than the brute-force approach.
Requires careful implementation to handle the deque operations and edge cases correctly.

Solutions

Solution

1class Solution {2public3  int shortestSubarray(int[] nums, int k) {4    int n = nums.length;5    long[] s = new long[n + 1];6    for (int i = 0; i < n; ++i) {7      s[i + 1] = s[i] + nums[i];8    }9    Deque<Integer> q = new ArrayDeque<>();10    int ans = n + 1;11    for (int i = 0; i <= n; ++i) {12      while (!q.isEmpty() && s[i] - s[q.peek()] >= k) {13        ans = Math.min(ans, i - q.poll());14      }15      while (!q.isEmpty() && s[q.peekLast()] >= s[i]) {16        q.pollLast();17      }18      q.offer(i);19    }20    return ans > n ? -1 : ans;21  }22}

1function shortestSubarray ( nums , k ) { const [ n , MAX ] = [ nums . length , Number . POSITIVE_INFINITY ]; const s = Array ( n + 1 ). fill ( 0 ); const q = []; 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 ; }

1class Solution {2public:3  int shortestSubarray(vector<int> &nums, int k) {4    int n = nums.size();5    vector<long> s(n + 1);6    for (int i = 0; i < n; ++i)7      s[i + 1] = s[i] + nums[i];8    deque<int> q;9    int ans = n + 1;10    for (int i = 0; i <= n; ++i) {11      while (!q.empty() && s[i] - s[q.front()] >= k) {12        ans = min(ans, i - q.front());13        q.pop_front();14      }15      while (!q.empty() && s[q.back()] >= s[i])16        q.pop_back();17      q.push_back(i);18    }19    return ans > n ? -1 : ans;20  }21};

1class Solution:2    def shortestSubarray(self, nums: List[int], k: int) -> int: s = list(accumulate(nums, initial=0)) q = deque() ans = inf for i, v in enumerate(s): while q and v - s[q[0]] >= k: ans = min(ans, i - q . popleft()) while q and s[q[- 1]] >= v: q . pop() q . append(i) return - 1 if ans == inf else ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem