Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 10 Dec, 2020

Shortest subarray with sum at least K

Moderate
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’. 
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

Approaches

01 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'