862. Shortest Subarray with Sum at Least K
Problem Description
The problem asks us to find the length of the shortest contiguous subarray within an integer array nums
such that the sum of its elements is at least a given integer k
. If such a subarray does not exist, we are to return -1
. The attention is on finding the minimum-length subarray that meets or exceeds the sum condition.
Intuition
To solve this efficiently, we utilize a monotonic queue and prefix sums technique. The intuition behind using prefix sums is that they allow us to quickly calculate the sum of any subarray in constant time. This makes the task of finding subarrays with a sum of at least k
much faster, as opposed to calculating the sum over and over again for different subarrays.
A prefix sum array s
is an array that holds the sum of all elements up to the current index. So for any index i
, s[i]
is the sum of nums[0] + nums[1] + ... + nums[i-1]
.
To understand the monotonic queue, which is a Double-Ended Queue (deque) in this case, let's look at its properties:
- It is used to maintain a list of indices of prefix sums in increasing order.
- When we add a new prefix sum, we remove all the larger sums at the end of the queue because the new sum and any future sums would always be better choices (smaller subarray) for finding a subarray of sum
k
. - We also continuously check if the current prefix sum minus the prefix sum at the start of the queue is at least
k
. If it is, we found a candidate subarray, and updateans
with the subarray's length. Then we can pop that element off the queue since we've already considered this subarray and it won't be needed for future calculations.
In summary, the prefix sums help us quickly compute subarray sums, and the monotonic queue lets us store and traverse candidate subarray ranges efficiently, ensuring we always have the smallest length subarray that meets the sum condition, thus arriving at the optimal solution.
Learn more about Queue, Binary Search, Prefix Sum, Sliding Window, Monotonic Queue and Heap (Priority Queue) patterns.
Solution Approach
The solution makes use of prefix sums and a monotonic queue, specifically a deque, to achieve an efficient algorithm to find the shortest subarray summing to at least k
. Let's explore the steps involved:
-
Prefix Sum Calculation: We initiate the computation by creating a list called
s
that contains the cumulative sum of thenums
list, by using theaccumulate
function with aninitial
parameter set to0
. This denotes that the first element ofs
is0
and is a requirement to consider subarrays starting at index0
. -
Initialization: A deque
q
is initialized to maintain the monotonic queue of indices. A variableans
is initialized toinf
(infinity) which will later store the smallest length of a valid subarray. -
Iterate Over Prefix Sums: We iterate over each value
v
in the prefix sums arrays
and its indexi
. -
Deque Front Comparison: While there are elements in
q
and the current prefix sumv
minus the prefix sum atq[0]
(the front of the deque) is greater than or equal tok
, we've found a subarray that meets the requirement. We then compute its lengthi - q.popleft()
and updateans
with the minimum ofans
and this length. Thepopleft()
operation removes this index from the deque as it is no longer needed. -
Deque Back Optimization: Before appending the current index
i
toq
, we pop indices from the back of the deque if their corresponding prefix sums are greater than or equal tov
because these are not conducive to the smallest length requirement and will not be optimal candidates for future comparisons. -
Index Appending: Append the current index
i
toq
. This index represents the right boundary for the potential subarray sums evaluated in future iterations.
After the loop, two cases may arise:
- If
ans
remainsinf
, it means no valid subarray summing to at leastk
was found, so we return-1
. - Otherwise, we return the value stored in
ans
as it represents the length of the shortest subarray that fulfills the condition.
Overall, the algorithm smartly maintains a set of candidate indices for the start of the subarray in a deque, ensuring that only those that can potentially give a smaller length subarray are considered. The key here is to understand how the prefix sum helps us quickly calculate the sum of a subarray and how the monotonically increasing property of the queue ensures we always get the shortest length possible. The use of these data structures makes the solution capable of working in O(n) time complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example. Suppose we have the following array and target sum k
:
nums = [2, 1, 5, 2, 3, 2] k = 7
We want to find the length of the smallest contiguous subarray with a sum greater than or equal to 7
. Here's how we would apply the solution approach:
-
Prefix Sum Calculation: We compute the prefix sum array
s
:s = [0, 2, 3, 8, 10, 13, 15]
Notice that
s[0]
is0
because we've added it artificially to account for subarrays starting at index 0. -
Initialization: We create a deque
q
to maintain indices of prefix sums:q = []
And initialize
ans
toinf
:ans = inf
-
Iterate Over Prefix Sums: We iterate over
s
, looking for subarrays that sum up to at leastk
. -
Deque Front Comparison: As we proceed, when we reach
s[3] = 8
(considernums[0..2]
), we find it is greater than or equal tok
. Theq
is empty, so we just move on. -
Deque Back Optimization: Before appending index
3
toq
, we don't remove anything fromq
because it's still empty. So we append3
intoq
. -
Index Appending: Our
q
is now[3]
.Continuing the iteration, we eventually come to
s[5] = 13
, which is the sum up tonums[0..4]
.We have a non-empty
q
, ands[5] - s[q[0]] = 13 - 8 = 5
, which is not greater than or equal tok
. So we can't pop anything from the queue yet. -
Once we reach
s[6] = 15
, we notice that15 - 8 = 7
is exactly ourk
. We then calculate the subarray length6 - q.popleft() = 6 - 3 = 3
. Now theans
becomes3
, the smallest subarray[5, 2, 3]
found so far. -
Deque Back Optimization is also done each time before we append a new index, which keeps the indices in the deque monotonically increasing in sums.
After considering all elements in s
, our ans
is 3
, as no smaller subarray summing to at least 7
is found. So we return 3
as the length of the shortest subarray. If ans
was still infinity
, we would return -1
indicating no such subarray was found.
Solution Implementation
1from collections import deque
2from itertools import accumulate
3from math import inf
4
5class Solution:
6 def shortest_subarray(self, nums: List[int], k: int) -> int:
7 # Calculate the prefix sums of nums with an initial value of 0
8 prefix_sums = list(accumulate(nums, initial=0))
9 # Initialize a double-ended queue to store indices
10 indices_deque = deque()
11 # Set the initial answer to infinity, as we are looking for the minimum
12 min_length = inf
13
14 # Enumerate over the prefix sums to find the shortest subarray
15 for current_index, current_sum in enumerate(prefix_sums):
16 # If the current_sum minus the sum at the front of the deque is at least k,
17 # update the min_length and pop from the deque
18 while indices_deque and current_sum - prefix_sums[indices_deque[0]] >= k:
19 min_length = min(min_length, current_index - indices_deque.popleft())
20 # Remove indices from the back of the deque if their prefix sums are greater
21 # than or equal to current_sum, as they are not useful anymore
22 while indices_deque and prefix_sums[indices_deque[-1]] >= current_sum:
23 indices_deque.pop()
24 # Add the current index to the back of the deque
25 indices_deque.append(current_index)
26
27 # Return -1 if no such subarray exists, otherwise the length of the shortest subarray
28 return -1 if min_length == inf else min_length
29
1class Solution {
2
3 // Function to find the length of the shortest subarray with a sum at least 'k'
4 public int shortestSubarray(int[] nums, int k) {
5 int n = nums.length; // Get the length of the input array
6 long[] prefixSums = new long[n + 1]; // Create an array to store prefix sums
7
8 // Calculate prefix sums
9 for (int i = 0; i < n; ++i) {
10 prefixSums[i + 1] = prefixSums[i] + nums[i];
11 }
12
13 // Initialize a deque to keep track of indices
14 Deque<Integer> indexDeque = new ArrayDeque<>();
15 int minLength = n + 1; // Initialize the minimum length to an impossible value (larger than the array itself)
16
17 // Iterate over the prefix sums
18 for (int i = 0; i <= n; ++i) {
19
20 // While the deque is not empty, check if the current sum minus the front value is >= k
21 while (!indexDeque.isEmpty() && prefixSums[i] - prefixSums[indexDeque.peek()] >= k) {
22 minLength = Math.min(minLength, i - indexDeque.poll()); // If true, update minLength
23 }
24
25 // While the deque is not empty, remove all indices from the back that have a prefix sum greater than or equal to the current sum
26 while (!indexDeque.isEmpty() && prefixSums[indexDeque.peekLast()] >= prefixSums[i]) {
27 indexDeque.pollLast();
28 }
29
30 // Add the current index to the deque
31 indexDeque.offer(i);
32 }
33
34 // If minLength is still greater than the length of the array, there is no valid subarray, return -1
35 return minLength > n ? -1 : minLength;
36 }
37}
38
1#include <vector>
2#include <deque>
3#include <algorithm> // For std::min
4
5class Solution {
6public:
7 // Function to find the length of shortest subarray with sum at least K
8 int shortestSubarray(vector<int>& nums, int k) {
9 int n = nums.size();
10 // Prefix sum array with an extra slot for ease of calculations
11 vector<long> prefixSum(n + 1, 0);
12 // Calculate the prefix sums
13 for (int i = 0; i < n; ++i) {
14 prefixSum[i + 1] = prefixSum[i] + nums[i];
15 }
16
17 // Double ended queue to store indices of the prefix sums
18 deque<int> indices;
19 // Initialize the answer with maximum possible length + 1
20 int minLength = n + 1;
21
22 // Loop through all prefix sum entries
23 for (int i = 0; i <= n; ++i) {
24 // If the current subarray (from front of deque to i) has sum >= k
25 while (!indices.empty() && prefixSum[i] - prefixSum[indices.front()] >= k) {
26 // Update the minimum length
27 minLength = min(minLength, i - indices.front());
28 // Pop the front index since we found a shorter subarray ending at index i
29 indices.pop_front();
30 }
31 // While the last index in the deque has a prefix sum larger than or equal to current
32 // we can discard it, since better candidates for subarray start are available
33 while (!indices.empty() && prefixSum[indices.back()] >= prefixSum[i]) {
34 indices.pop_back();
35 }
36 // Add current index to the deque
37 indices.push_back(i);
38 }
39
40 // If no valid subarray is found, minLength remains > n. Return -1 in that case.
41 return minLength > n ? -1 : minLength;
42 }
43};
44
1// Importing required modules
2import { Deque } from 'collections/deque'; // Assume a Deque implementation like "collections.js" or similar
3
4// Function to find the length of shortest subarray with sum at least K
5function shortestSubarray(nums: number[], k: number): number {
6 let n = nums.length;
7 // Prefix sum array with an extra slot for ease of calculations
8 let prefixSum: number[] = new Array(n + 1).fill(0);
9 // Calculate the prefix sums
10 for (let i = 0; i < n; ++i) {
11 prefixSum[i + 1] = prefixSum[i] + nums[i];
12 }
13
14 // Double-ended queue to store indices of the prefix sums
15 let indices: Deque<number> = new Deque<number>();
16 // Initialize the answer with maximum possible length + 1
17 let minLength = n + 1;
18
19 // Loop through all prefix sum entries
20 for (let i = 0; i <= n; ++i) {
21 // If the current subarray (from front of deque to i) has a sum >= k
22 while (!indices.isEmpty() && prefixSum[i] - prefixSum[indices.peekFront()!] >= k) {
23 // Update the minimum length
24 minLength = Math.min(minLength, i - indices.peekFront()!);
25 // Pop the front index since we found a shorter subarray ending at index i
26 indices.shift();
27 }
28 // While the last index in the deque has a prefix sum larger than or equal to the current
29 // we can discard it, since better candidates for subarray start are available
30 while (!indices.isEmpty() && prefixSum[indices.peekBack()!] >= prefixSum[i]) {
31 indices.pop();
32 }
33 // Add current index to the deque
34 indices.push(i);
35 }
36
37 // If no valid subarray is found, minLength remains > n. Return -1 in that case.
38 return minLength > n ? -1 : minLength;
39}
40
41// Example usage:
42// const nums = [2, -1, 2];
43// const k = 3;
44// console.log(shortestSubarray(nums, k)); // Output should be 3
45
Time and Space Complexity
The given Python code is for finding the length of the shortest contiguous subarray whose sum is at least k
. The code uses the concept of prefix sums and a monotonic queue to keep track of potential candidates for the shortest subarray.
Time Complexity
The time complexity of the code is O(N)
, where N
is the length of the input array nums
.
This is because:
- The prefix sum array
s
is computed usingitertools.accumulate
, which is a single pass through the array, thus takingO(N)
time. - The deque
q
is maintained by iterating through each element of the array once. Each element is added and removed from the deque at most once. Since the operations of adding to and popping from a deque areO(1)
, the loop operations are alsoO(N)
in total. - Inside the loop,
q.popleft()
andq.pop()
are each called at most once per iteration, and as a result, each element innums
contributes at mostO(1)
to the time complexity.
Space Complexity
The space complexity of the code is O(N)
as well:
- The prefix sum array
s
requiresO(N)
space. - The deque
q
potentially stores indices from the entire array in the worst-case scenario. In the worst case, it could hold all indices innums
, also requiringO(N)
space. - Apart from these two data structures, the code uses a constant amount of space for variables such as
ans
andv
, which does not depend on the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Want a Structured Path to Master System Design Too? Donāt Miss This!