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 <iostream>
2#include <vector>
3#include <deque>
4#include <limits>
5using namespace std;
6
7int shortestSubarray(vector<int>& nums, int k) {
8 deque<int> dq;
9 int n = nums.size();
10 vector<long> prefixSum(n + 1, 0);
11 for (int i = 0; i < n; ++i) {
12 prefixSum[i + 1] = prefixSum[i] + nums[i];
13 }
14 int result = INT_MAX;
15 for (int i = 0; i <= n; ++i) {
16 while (!dq.empty() && prefixSum[i] - prefixSum[dq.front()] >= k) {
17 result = min(result, i - dq.front());
18 dq.pop_front();
19 }
20 while (!dq.empty() && prefixSum[i] <= prefixSum[dq.back()])
21 dq.pop_back();
22 dq.push_back(i);
23 }
24 return result == INT_MAX ? -1 : result;
25}
26
27int main() {
28 vector<int> nums = {2, -1, 2};
29 int k = 3;
30 cout << shortestSubarray(nums, k) << endl; // Output: 3
31 return 0;
32}The function uses a deque to find the shortest subarray with a sum of at least k. The prefix sum array helps keep track of cumulative sums. For each prefix sum index, the algorithm checks whether it can form a valid subarray with a previous prefix sum in the deque. It also maintains the deque in increasing order of prefix sums to justify the condition.
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.
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.