Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Shortest subarray with sum at least K

Moderate
0/80
Average time to solve is 15m
8 upvotes
Asked in companies
PaypalPaytm (One97 Communications Limited)Apple

Problem statement

Given an array/list 'ARR' of integers and an integer ‘K’. You are supposed to return the length of the shortest subarray that has a sum greater than or equal to ‘K’. If there is no subarray with a sum greater than or equal to K, then return -1.

Note :
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’. 
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
1 <= T <= 50
2 <= N <= 10^4
1 <= K <= 10^9
-10^5 <= ARR[i] <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
5 12
3 6 7 4 3
4 8
7 2 5 4
Sample Output 1 :
2
2
Explanation of Sample Input 1 :
In the first test case, the subarray from index 1 to index 2, i.e. {6, 7} has sum 13, which is greater than 12; hence the answer is 2.

In the second test case, the subarray from index 0 to index 1, i.e. {7, 2} has sum 9 which is greater than 8; also the subarray from index 2 to index 3, i.e. {5, 4} has sum 9 which is greater than 8; hence the answer is 2.
Sample Input 2 :
2
5 6
1 -4 2 2 3
5 30
3 5 6 2 9
Sample Output 2 :
3
-1
Explanation of Sample Input 2 :
In the first test case, the subarray from index 2 to index 4, i.e. {2, 2, 3} has sum 7, which is greater than 6; hence the answer is 3.

In the second test case, no subarray has a sum greater than or equal to 30; hence the answer is -1.
Full screen
Console