862. Shortest Subarray with Sum at Least K

HardQueueArrayBinary SearchPrefix SumSliding WindowMonotonic QueueHeap (Priority Queue)

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 update ans 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 the nums list, by using the accumulate function with an initial parameter set to 0. This denotes that the first element of s is 0 and is a requirement to consider subarrays starting at index 0.
Initialization: A deque q is initialized to maintain the monotonic queue of indices. A variable ans is initialized to inf (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 array s and its index i.
Deque Front Comparison: While there are elements in q and the current prefix sum v minus the prefix sum at q[0] (the front of the deque) is greater than or equal to k, we've found a subarray that meets the requirement. We then compute its length i - q.popleft() and update ans with the minimum of ans and this length. The popleft() operation removes this index from the deque as it is no longer needed.
Deque Back Optimization: Before appending the current index i to q, we pop indices from the back of the deque if their corresponding prefix sums are greater than or equal to v 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 to q. This index represents the right boundary for the potential subarray sums evaluated in future iterations.

After the loop, two cases may arise:

If ans remains inf, it means no valid subarray summing to at least k 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 Evaluator

Example 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] is 0 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 to inf:
```
ans = inf
```
Iterate Over Prefix Sums: We iterate over s, looking for subarrays that sum up to at least k.
Deque Front Comparison: As we proceed, when we reach s[3] = 8 (consider nums[0..2]), we find it is greater than or equal to k. The q is empty, so we just move on.
Deque Back Optimization: Before appending index 3 to q, we don't remove anything from q because it's still empty. So we append 3 into q.
Index Appending: Our q is now [3].

Continuing the iteration, we eventually come to s[5] = 13, which is the sum up to nums[0..4].

We have a non-empty q, and s[5] - s[q[0]] = 13 - 8 = 5, which is not greater than or equal to k. So we can't pop anything from the queue yet.
Once we reach s[6] = 15, we notice that 15 - 8 = 7 is exactly our k. We then calculate the subarray length 6 - q.popleft() = 6 - 3 = 3. Now the ans becomes 3, 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 using itertools.accumulate, which is a single pass through the array, thus taking O(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 are O(1), the loop operations are also O(N) in total.
Inside the loop, q.popleft() and q.pop() are each called at most once per iteration, and as a result, each element in nums contributes at most O(1) to the time complexity.

Space Complexity

The space complexity of the code is O(N) as well:

The prefix sum array s requires O(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 in nums, also requiring O(N) space.
Apart from these two data structures, the code uses a constant amount of space for variables such as ans and v, which does not depend on the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know