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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
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 LinkedList<int> deque = new LinkedList<int>();
12 int result = int.MaxValue;
13 for (int i = 0; i <= n; ++i) {
14 while (deque.Count > 0 && prefixSum[i] - prefixSum[deque.First.Value] >= k) {
15 result = Math.Min(result, i - deque.First.Value);
16 deque.RemoveFirst();
17 }
18 while (deque.Count > 0 && prefixSum[i] <= prefixSum[deque.Last.Value])
19 deque.RemoveLast();
20 deque.AddLast(i);
21 }
22 return result == int.MaxValue ? -1 : result;
23 }
24
25 public static void Main(string[] args) {
26 Solution sol = new Solution();
27 int[] nums = {2, -1, 2};
28 int k = 3;
29 Console.WriteLine(sol.ShortestSubarray(nums, k)); // Output: 3
30 }
31}The C# implementation features a LinkedList to simulate a deque. As it iterates over each element of the prefix sum array, it seeks to identify the shortest subarray whose sum achieves or exceeds k. Indices relevant for this calculation are kept and managed within the deque to preserve optimal length assessments.
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.
public class ShortestSubarrayBruteForce {
public int ShortestSubarray(int[] nums, int k) {
int minLength = int.MaxValue;
for (int start = 0; start < nums.Length; ++start) {
int sum = 0;
for (int end = start; end < nums.Length; ++end) {
sum += nums[end];
if (sum >= k) {
minLength = Math.Min(minLength, end - start + 1);
break;
}
}
}
return minLength == int.MaxValue ? -1 : minLength;
}
public static void Main(string[] args) {
ShortestSubarrayBruteForce sol = new ShortestSubarrayBruteForce();
int[] nums = {2, -1, 2};
int k = 3;
Console.WriteLine(sol.ShortestSubarray(nums, k)); // Output: 3
}
}In C#, this brute force solution uses nested loops to explore each subarray beginning at every index. It seeks a summation that meets or surpasses k, against which minimal subarray lengths can be compared and updated, where applicable. Although functional, scalability is limited by complexity.