Last Updated: 10 Dec, 2020

Shortest subarray with sum at least K

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

02 Approach

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:

  1. Calculate the 'PREFIX_SUM' array by iterating through the given array/list, let’s say our current index is 'CURR' then we will calculate PREFIX_SUM[CURR] by adding PREFIX_SUM[CURR-1] and ARR[CURR-1].
  2. Define a double-ended queue to maintain the elements of the 'PREFIX_SUM' array/list in increasing order, let’s say 'INCREASING_PREFIX'.
  3. Now iterate through the 'PREFIX_SUM' array, let’s say our current index is ‘i’.
    1. Let’s say the element at the back of 'INCREASING_PREFIX' is 'PREVIOUS_ELEMENT'. Now we will keep popping elements from the rear of the queue till the PREFIX_SUM[PREVIOUS_ELEMENT] is greater than the PREFIX_SUM[i]. We will do this because to insert the current index into the double-ended queue, we need to remove all the indices from the double-ended queue at which the 'PREFIX_SUM' has a value greater than the PREFIX_SUM[i].
    2. Let’s say the element at the front of the queue is 'FIRST_ELEMENT'. Now we will keep popping elements from the front of the queue while PREFIX_SUM[i] - PREFIX_SUM[FIRST_ELEMENT] is greater than or equal to K, we also update the  ‘SUBARRAY_SUM_K’  as the min('SUBARRAY_SUM_K', i-FIRST_ELEMENT). We can pop this element because even if a subarray starting at ‘FIRST_ELEMENT’ and ending at an index greater than ‘i’ has a sum greater than ‘K’, then also the length of the subarray will always be greater than the (i-FIRST_ELEMENT). Hence, that subarray will never be the shortest subarray in the length.
    3. Push ‘i’ to the back of the double-ended queue('INCREASING_PREFIX').
  4. If the value of ‘SUBARRAY_SUM_K’ is still +ve infinity (i.e. INT_MAX), then return -1 because we could not find any such subarray whose sum is greater than or equal the ‘K’, otherwise, return the value of ‘SUBARRAY_SUM_K’.