Shortest subarray with sum at least K

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

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 )
Input Format : 
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.
Output Format : 
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’.
Note : 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
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.
Hint

Can you try to find the sum of all possible subarrays?

Approaches (2)
Brute Force Approach

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:

  1. Initialise a variable ‘SUBARRAY_SUM_K’ to +ve infinity(INT_MAX). We will use this variable to store the length of the shortest subarray with a sum greater than or equal to ‘K’.
  2. We will iterate through the given array/list and pivot each element of the array/list as the starting point of the subarray, let’s say the index of this element is ‘i’.
    1. We will use the variable 'SUM', which will be initialised to 0. 'SUM' will store the sum of array/list elements from i-th position to the previous of the current position.
    2. Iterate from index ’i’ till the end of the array, let’s say our current index is ‘j’.
    3. Add the value of the element at index ‘j’ to “sum”.
    4. If the value of 'SUM' is greater than K
      1. If the length of the current subarray(j-i+1) is smaller than 'SUBARRAY_SUM_K' then update the value of  ‘SUBARRAY_SUM_K’.
      2. Break the loop because if we proceed further then we will only get subarrays with greater length.
  3. If the value of ‘SUBARRAY_SUM_K’ is INT_MAX then return -1 because we didn’t find any subarray whose sum is greater than or equal to ‘K’. Else, return the value of 'SUBARRAY_SUM_K'
Time Complexity

O(N^2), where ‘N’ is the number of elements in the given array/list.

 

We are iterating through the given array/list and pivoting each element. There are ‘N’ elements to pivot, and for each pivot element, we will iterate till the end of the array which will take O(N) time. Thus, the overall time complexity is O(N^2).

Space Complexity

O(1)

 

We are not using any extra space apart from a few variables. Thus, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Shortest subarray with sum at least K
Full screen
Console