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.
1import java.util.Deque;
2import java.util.LinkedList;
3
4public class ShortestSubarraySum {
5 public int shortestSubarray(int[] nums, int k) {
6 int n = nums.length;
7 long[] prefixSum = new long[n + 1];
8 for (int i = 0; i < n; ++i) {
9 prefixSum[i + 1] = prefixSum[i] + nums[i];
10 }
11 Deque<Integer> dq = new LinkedList<>();
12 int result = Integer.MAX_VALUE;
13 for (int i = 0; i <= n; ++i) {
14 while (!dq.isEmpty() && prefixSum[i] - prefixSum[dq.peekFirst()] >= k) {
15 result = Math.min(result, i - dq.pollFirst());
16 }
17 while (!dq.isEmpty() && prefixSum[i] <= prefixSum[dq.peekLast()])
18 dq.pollLast();
19 dq.addLast(i);
20 }
21 return result == Integer.MAX_VALUE ? -1 : result;
22 }
23
24 public static void main(String[] args) {
25 ShortestSubarraySum solver = new ShortestSubarraySum();
26 int[] nums = {2, -1, 2};
27 int k = 3;
28 System.out.println(solver.shortestSubarray(nums, k)); // Output: 3
29 }
30}The Java function calculates a prefix sum for the input array and utilizes a Deque to manipulate indices that could potentially form the shortest subarray with a sum of at least k. It maintains the deque such that it only contains indices that allow the subtraction of current prefix sums to achieve k.
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 brute force Java approach attempts every subarray possible from each index, adding elements one by one until the subarray sum is at least k. While thorough, its O(n^2) complexity means this method is mainly of educational value for understanding subarray dynamics under specific conditions.