Shortest Subarray with at least K as sum
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
In this problem, we find the length of the Shortest Subarray with at least K as sum. This can be solved in O(N) time complexity. This brings in the ideas of Monotonic Queue and Sliding Window.
Table of contents:
- Problem Statement
- How to approach?
- Brute Force approach
- How to Optimize?
Problem Statement
Return the length of the shortest, non-empty, contiguous subarray of nums with sum at least k.
If there is no non-empty subarray with sum at least k, return -1.
Example 1:
Input: nums = [1], k = 1
Output: 1
Example 2:
Input: nums = [1,2], k = 4
Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3
Output: 3
Constraints:
1 <= nums.length <= 50000
-105 <= nums[i] <= 105
1 <= k <= 109
How to approach?
Intution :
- We will start with a brute force solution. Checking for each subarray.
- Now, we will use two pointer technique for implementing our sliding window.
- Modify our sliding Window solution to reach the Deque solution.
Brute Force approach
Here, we are asked to find a subarray that satisfies the given condition.
- So try all non-empty subarrays.
- Check if a particular subarray sum is at least k.
- If so try to update the shortest possible length of subarray with sum >= K.
For checking sum of a subarray, you can use can create a prefix sum array, and get sum in constant time. But it will require extra space O(N).
But instead, we can store sum as we iterate through our subarray.
Pseudo Code :
Following is the pseudocode:
Initialize variable min to Integer.MAX_VALUE
if size of array == 1 and first element >= K return 1
if size of array == 1 reutrn -1
for i in range 0 to A.length - 1
initialize sum to A[i]
if sum >= K return 1
for j in range i + 1 to A.length - 1
increase sum by A[j]
if sum >= K update min
return min
Following is the implementation in Java:
class Solution {
public int shortestSubarray(int[] A, int K) {
int min = Integer.MAX_VALUE;
// if we have only one element with value >= K
if (A.length == 1 && A[0] >= K) {
return 1;
}
// we have only one element but with value < K
if (A.length == 1) {
return -1;
}
// i -> start of our subarray
for (int i = 0; i < A.length; i++){
int sum = A[i];
// best possible length found, so return
if (sum >= K) {
return 1;
}
// j -> end of our subarray
for (int j = i + 1; j < A.length; j++){
sum += A[j];
// found a subarray with sum >= K, so try updating min value
if (sum >= K) {
min = Math.min(min, j - i + 1);
}
}
}
if (min != Integer.MAX_VALUE) {
return min;
}
// found no valid subarray with sum >= K
return -1;
}
}
Assuming N to be the size of given input array.
Time Complexity : O(N^2), since we have (N^2) subarrays in total.
Space Complexity : O(1), no extra space is used.
This would cause TLE.
How to Optimize?
We can use Sliding Window technique.
Intution :
- We simply maintain two pointers (i, j).
- Keep increasing j until our sum for subarray[i, j] >= K.
- Now we try update our minimum length.
- Now keep increase i and update our minimum length, until subarray[i, j] voilates the condition subarray[i, j] >= K.
- Now we again start increasing j.
Example :
Array[] = [3, 4, 4, 1, 3, 5, 2, 3]
Target : 5
So, it runs as follows-
1.Whenever Current Sum >= K, try to update Minimum Length.
2.Initialize Minimum Length = Integer.MAX_VALUE
Note : We can even take min length as N, since that is the max possible size of subarray.
Current Array Current Sum
[3] 3
[3, 4] 7
[4] 4
[4, 4] 8
[4] 4
[4, 1] 5
[1] 1
[1, 3] 4
[1, 3, 5] 9
[3, 5] 8
[5] 5
Here we can stop, as we found best possible length.
.
.
.
But what if we had negative numbers, as (-105 <= nums[i] <= 105).
Example :
Array[] = [2, 1, -2, 5, 2]
Target : 5
Minimum Length = Integer.MAX_VALUE
Current Array Current Sum
[2] 2
[2, 1] 3
[2, 1, -2] 1
[2, 1, -2, 5] 6
[1, -2, 5] 4
[-2, 5] 3
[-2, 5, 2] 5
[5, 2] 7
[2] 2
So our min length should be 2
Right??
NO.
Actually we can have min length of 1, with only one element 5.
So it doesn't work for negative values.
Now, lets try to modify our two pointer approach using monotonic queue.
Intution :
- We should think of prefix sum for these subarray problems.
- Maintain a monotonic increasing queue.
- Keep checking if front element of the queue is satisfying the requirement.
- If it satisfies, we pop front, because we found the best length starting with queue front.
- Before we put the current prefix sum into the queue, we keep popping out the element from the queue greater than current prefix sum , because there won't be any better solution with the bigger prefix sum.
Explaination :
***A monotonic Queue(deque in java) is a data structure the elements from the front to the end is strictly either increasing or decreasing. ***
Here we use strictly increasing monotonic Queue, to store the possible indices with an increasing sum.
Three main points in this solution:
-
We have a prefix array to get range sums in constant time, since we are jumping our start values or the values in the deque are not contigious, we can't keep track of running sum.
-
First while loop
**B[j] - B[dq.getFirst()] >= K**, once we have found an ending j such that subarray[deque first index, j] >= K, now we can remove first element of deque since there can't be any better subarray, starting with deque first element and the deque has indices in increasing order. -
Second while loop,
**B[j] <= B[dq.getLast()]**, because we want our monoqueue to store indices with increasing sum only.
Wait!
I know it's really hard to absorb third point.
So let me make it really simple for you by a simple situation.
Here
Monoqueue(M) represent indices stored in increasing order
Sums represent sum of elements of subarray[monoqueue first index, j].
Sums [ 5 10 6 -------------------- 70 --------- ]
Monoqueue(M) [ 0 1 2 -------------------- 10 --------- ]
Here we can see that index 2 is a better candidate than index 1, in terms of sum and length.
Sum comparasion
70 - 6 = 64 forming a subarray with sum 64
whereas 70 - 10 = 60 forming a subarray with sum 64
Length comparasion
Also 10 - 2 = 8 and 10 - 1 = 9
So we removed index 1, when found a decreased sum.
Sums [ 5 6 -------------------- 70 --------- ]
Monoqueue(M) [ 0 2 -------------------- 10 --------- ]
Pseudo Code :
Initialize variable N to A.length
Initialize an array of length N + 1
for i in range 0 to N - 1
update B[i + 1] to previous prefix sum + curr element
Initialize variable res to N + 1
Initialize a deque of integer
for j in range 0 to N
while queue is not empty and prefix sum till curr index - prefix sum till queue first index >= K
update res
while queue is not empty and prefix sum till curr index <= prefix sum till queue last index
pop last element of queue
add j to queue
return res
class Solution {
public int shortestSubarray(int[] A, int K) {
int N = A.length;
// to store prefix sums
int[] B = new int[N + 1];
for (int i = 0; i < N; i++) {
B[i + 1] = B[i] + A[i];
}
int res = N + 1;
// our monotonic increasing queue
Deque<Integer> dq = new LinkedList<>();
for (int j = 0; j < N + 1; j++) {
while (dq.size() > 0 && B[j] - B[dq.getFirst()] >= K) {
res = Math.min( res , j - dq.pollFirst() );
}
while (dq.size() > 0 && B[j] <= B[dq.getLast()]) {
dq.pollLast();
}
// add the current prefix sum till j.
dq.addLast(j);
}
return res == N + 1 ? -1 : res;
}
}
Time Complexity : O(N), since we are doing at most two operation for each element in array, adding to deque and removing from deque, and we haven N elements. So at most 2*N operations, so O(N).
Space Complexity : O(N), we use deque to store elements, and at most N elements can be stored.
Additional techniques to solve a problem in general:
1 : Using QuickSelect for optimizations in finding Kth minimum/maximum. QuickSelect has average time complexity of O(N). In quickSelect, we do not do complete quicksort, instead we stop at a point where pivot itself is the Kth largest/smallest element, otherwise recurse for either left or right based on question.
Worst case : O(N^2).
2 : Finding bridge in a graph, we maintain two things for each node, first is node_id which is assigned using DFS, and second is a low-link value which is assigned while returning from DFS call.
How to know if an edge (from A to B) is a bridge??
If node_id of A < low-link value of B.
"I hope you enjoyed this article at OpenGenus, and was useful for you all"!!
Thank you all!
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.