Leetcode 862. Shortest Subarray with Sum at Least K
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:
- Compute the prefix sums for all the indices in the given array.
- Initialize a deque data structure.
- Iterate over the prefix_sums, for each
prefix[i]
.- While the deque is not empty and
prefix[i]
minusprefix[deque.front()]
is greater or equal toK
, keep popping elements from the front of the queue and in each step minimize the answer withi - deque.front()
. - It is done because it means we have found a shorter sub-array ending at
i
with sum at leastK
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 toprefix[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 indexdeque.back()
.Thus, every index will be pushed and popped at most once from deque.
- While the deque is not empty and
- At the end, if
ans
is within the array lengthn
, returnans
. 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.