Sponsored
Sponsored
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.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), for the prefix sum array and deque.
1#include <stdio.h>
2#include <limits.h>
3#include <stdlib.h>
4
5int shortestSubarray(int* nums, int numsSize, int k) {
6 int* prefixSum = (int*) malloc((numsSize + 1) * sizeof(int));
7 prefixSum[0] = 0;
8 for (int i = 0; i < numsSize; ++i) {
9 prefixSum[i + 1] = prefixSum[i] + nums[i];
10 }
11
12 int deque[numsSize + 1];
13 int front = 0, back = 0;
14 int result = INT_MAX;
15
16 for (int i = 0; i <= numsSize; ++i) {
17 while (front < back && prefixSum[i] - prefixSum[deque[front]] >= k) {
18 if (result > i - deque[front])
19 result = i - deque[front];
20 front++;
21 }
22 while (front < back && prefixSum[i] <= prefixSum[deque[back - 1]])
23 back--;
24 deque[back++] = i;
25 }
26 free(prefixSum);
27 return result == INT_MAX ? -1 : result;
28}
29
30int main() {
31 int nums[] = {2, -1, 2};
32 int k = 3;
33 int result = shortestSubarray(nums, 3, k);
34 printf("%d\n", result); // Output: 3
35 return 0;
36}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.
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.
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.
1#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;
}The C++ solution takes a straightforward approach by evaluating all potential subarrays. For each starting index, it iterates the endpoint and calculates the subarray sum. Once it reaches a sum that's at least k, it checks if this is the minimal length found so far. While clear, this method is inefficient for large input sizes due to its quadratic time complexity.