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.
1from collections import deque
2
3def shortest_subarray(nums, k):
4 n = len(nums)
5 prefix_sum = [0] * (n + 1)
6 for i in range(n):
7 prefix_sum[i + 1] = prefix_sum[i] + nums[i]
8 dq = deque()
9 result = float('inf')
10 for i in range(n + 1):
11 while dq and prefix_sum[i] - prefix_sum[dq[0]] >= k:
12 result = min(result, i - dq.popleft())
13 while dq and prefix_sum[i] <= prefix_sum[dq[-1]]:
14 dq.pop()
15 dq.append(i)
16 return result if result != float('inf') else -1
17
18nums = [2, -1, 2]
19k = 3
20print(shortest_subarray(nums, k)) # Output: 3This Python implementation uses a deque to hold indices of prefix sums. As it iterates through the prefix sums, it checks whether removing the earliest index in the deque helps in achieving a valid subarray that sums to at least k. When it finds such an index, it calculates and potentially updates the shortest length of this subarray.
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.
Inside a nested loop structure, this JavaScript code iterates over every possible starting point for a subarray. It accumulates a running sum and updates the best length when the sum reaches or exceeds k. The language's native handling of large numbers assists with practical limits but does not alleviate the inherent inefficiency.