Problem Explanation

In this problem, we are given an array and a target sum. The task is to find the shortest subarray whose sum is at least the target sum. If no such subarray exists, we should return -1.

For instance: If the array is [2, -1, 2] and the target sum is 3, the shortest subarray with sum at least 3 is [2, -1, 2] itself, so the function should return length 3.

Solution Approach

The solution includes the use of prefix sum and a deque data structure (which is a double-ended queue).

The prefix sum stores the sum of all previous elements in the array at each index. This makes it easy to calculate the sum of any subarray.

The deque is used to store the indices of the elements in the prefix sum array. The deque will always hold a monotonically increasing sequence of indices.

Solution Steps

Here's the detailed step-by-step approach of the solution:

1. Compute the prefix sums for all the indices in the given array.
2. Initialize a deque data structure.
3. Iterate over the prefix_sums, for each prefix[i].
   • While the deque is not empty and prefix[i] minus prefix[deque.front()] is greater or equal to K, keep popping elements from the front of the queue and in each step minimize the answer with i - deque.front().
   • It is done because it means we have found a shorter sub-array ending at i with sum at least K compared to the previous sub-arrays. So, we don't need to consider the previous longer sub-arrays anymore.
   • While the deque is not empty and prefix[i] is less or equal to prefix[deque.back()], then pop elements from the back of the queue.
   • It is done because a better candidate of an index (smaller prefix[i]) is available for the future elements, so there is no need to keep the previous index deque.back().Thus, every index will be pushed and popped at most once from deque.
4. At the end, if ans is within the array length n, return ans. Otherwise, return -1, meaning that no valid sub-array was found.

The final time complexity is O(n), where n is the number of elements in the input array.

After explaining the solution, in the next steps, the solution will be provided in Python, Java, Javascript, C++, and C# programming languages.# Python Solution

1
2python
3from collections import deque
4
5def shortestSubarray(A, K):
6    n = len(A)
7    P = [0]
8    for x in A:
9        P.append(P[-1] + x)
10
11    # First index of prefix sums array which is greater than i
12    dq = deque()
13    ans = len(A) + 1
14    for i, x in enumerate(P):
15        while dq and x - P[dq[0]] >= K:
16            ans = min(ans, i - dq.popleft())
17        while dq and x <= P[dq[-1]]:
18            dq.pop()
19        dq.append(i)
20
21    if ans < n + 1:
22        return ans
23    else:
24        return -1
25
26print(shortestSubarray([2, -1, 2], 3)) # Output: 3

Java Solution

1
2java
3import java.util.Deque;
4import java.util.LinkedList;
5
6public class Solution {
7    public int shortestSubarray(int[] A, int K) {
8        int n = A.length;
9        long[] P = new long[n+1];
10        for (int i = 0; i < n; i++) {
11            P[i+1] = P[i] + A[i];
12        }
13        int ans = n+1;
14        Deque<Integer> dq = new LinkedList();
15        for (int i = 0; i < P.length; i++) {
16            while (!dq.isEmpty() && P[i] - P[dq.getFirst()] >= K) {
17                ans = Math.min(ans, i - dq.removeFirst());
18            }
19            while (!dq.isEmpty() && P[i] <= P[dq.getLast()]) {
20                dq.removeLast();
21            }
22            dq.addLast(i);
23        }
24        return ans < n + 1 ? ans : -1;
25    }
26    public static void main(String[] args) {
27        Solution solution = new Solution();
28        int[] A = {2, -1, 2};
29        System.out.println(solution.shortestSubarray(A, 3)); // Output: 3
30    }
31}

JavaScript Solution

1
2javascript
3function shortestSubarray(A, K) {
4let n = A.length;
5let P = new Array(n+1).fill(0);
6for(let i=0;i<n;i++)
7P[i+1] = P[i] + A[i];
8
9let deque = [];
10let ans = Number.MAX_SAFE_INTEGER;
11
12for(let i=0;i<P.length;i++) {
13while(deque.length && P[i] - P[deque[0]] >= K)
14ans = Math.min(ans, i - deque.shift());
15while(deque.length && P[i] <= P[deque[deque.length-1]])
16deque.pop();
17deque.push(i);
18}
19
20return (ans !== Number.MAX_SAFE_INTEGER) ? ans : -1;
21}
22
23console.log(shortestSubarray([2, -1, 2], 3));  // Output: 3

This Python, Java, and JavaScript solution makes use of a prefix sum and a deque data structure to find the shortest subarray with sum at least K, as defined in the problem. This method ensures O(n) time complexity.