An array ‘B’ is a subarray of an array ‘A’ if ‘B’ that can be obtained by deletion of, several elements(possibly none) from the start of ‘A’ and several elements(possibly none) from the end of ‘A’.
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.
The first line of each test case contains two integers separated by a single space ‘N’ and ‘K’ denoting the number of elements in the array/list, and the minimum required sum.
The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array/list.
For each test case, return a single integer that denotes the length of the shortest subarray with a sum greater than or equal to ‘K’.
You don’t need to print anything; It has already been taken care of. Just implement the given function.
1 <= T <= 50
2 <= N <= 10^4
1 <= K <= 10^9
-10^5 <= ARR[i] <= 10^5
Time Limit: 1 sec
The idea is to find all the sub-arrays and calculate the sum of each sub-arrays and then take the length of the smallest subarray with a sum greater than or equal to ‘K’.
The steps are as follows:
Let’s define an array/list 'PREFIX_SUM', where for any index ‘i’, PREFIX_SUM[i]= sum of the first (i-1) elements of the given array/list.
For calculating the sum of elements of any subarray with the starting index ‘i’ and ending index at ‘j’ we can simply do PREFIX_SUM[j]- PREFIX_SUM[i-1].
Now we need to find two indices ‘j’ and ‘i’ (j >= i) such that PREFIX_SUM[j]- PREFIX_SUM[i-1] >= K and (j-i+1) is minimum.
The idea is to use the fact that for finding two indices ‘j’ and ‘i (j >= i)’ such PREFIX_SUM[j]- PREFIX_SUM[i-1] >= K the ‘PREFIX_SUM’ array/list must be in increasing order. We will use a double-ended queue to maintain an increasing order of the ‘PREFIX_SUM’ array. Also, we will initialise a variable 'SUBARRAY_SUM_K' as +ve infinity (i.e. INT_MAX), and we will use this variable to store the shortest length of the subarray with a sum greater than K.
The steps are as follows:
Longest Subarray With Zero Sum
Merge Two Sorted Arrays Without Extra Space
Merge Two Sorted Arrays Without Extra Space
Ninja And The Strictly Increasing Array
Negative To The End
Find Duplicate in Array