Last Updated: 19 May, 2021

Rahul And Minimum Subarray

Moderate

Asked in companies

Solve now

Problem statement

Rahul is a programming enthusiast. He is currently learning about arrays/lists. One day his teacher asked him to solve a very difficult problem. The problem was to find the length of the smallest subarray(subarray is a contiguous part of an array/list) in a given array/list ‘ARR’ of size ‘N’ with its sum greater than a given value. If there is no such subarray return 0.

Example: Given an ‘ARR’: [1, 2, 21, 7, 6, 12] and a number ‘X’: 23. The length of the smallest subarray is 2 as the subarray is [21, 7].

Note: Here are multiple subarrays whose sum is greater than ‘X’ such as [1, 2, 21] or [7, 6, 12] but we have to choose the minimum length subarray.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two integers ‘N’ and ‘X’ that denote the size of the ‘ARR’ and the given value respectively.

The second line of each test case contains ‘N’ space-separated integers ‘A[i]’, these are the numbers present in our ‘ARR’.

Output Format:

For each test case, print an integer denoting the length of the minimum subarray whose sum is greater than ‘X’.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 10^2
1 <= N <= 10^3
1 <= X <= 10^9
0 <= A[i] <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea of this approach is to iterate the whole ‘ARR’ from start and find the sum of all the possible subarrays and find out the length of the minimum subarray whose sum is greater than the given value. We will use two loops and calculate the sum for all the possible subarrays and select the subarrays that match our given conditions.

Here is the algorithm:

Declare a variable ‘MIN_LENGTH’ which will contain the length of the minimum subarray.
Run a loop for ‘i’ = 0 to ‘N’:
- Declare a variable ‘CURRENT_SUM’ which will store the sum of all possible subarrays
- Run a loop for ‘j’ = ‘i’ + 1 to ‘N’:
  - Add the current element ‘ARR[j]’ to the sum ‘CURRENT_SUM’.
  - Compare the value of ‘CURRENTSUM’ with ‘TARGET’. If ‘CURRENT_SUM’ is greater than ‘TARGET’:
    - Update ‘MINLENGTH’ if ‘MIN_LENGTH’ is smaller than the length of the current subarray.
Finally, return ‘MIN_LENGTH’.

Solve now

02 Approach

As all the elements in the ‘ARR’ are positive, if a subarray has a sum greater than ‘TARGET’ then adding other elements to the current subarray will make the sum even greater. The idea is to start with an empty subarray and add elements to it until its sum is greater than ‘TARGET’. As soon as the sum is greater than ‘TARGET’ remove the starting element from the current sum.

Here is the algorithm:

Declare four variables ‘START_INDEX’, ‘END_INDEX’, ‘CURRENT_SUM’, and ‘MIN_LENGTH’ where ‘START_INDEX’ and ‘END_INDEX’ denote the indexes of the current subarray whose sum is stored in ‘CURRENT_SUM’ and ‘MIN_LENGTH’ denotes the length of the minimum subarray.
Run a loop from start to end of the ‘ARR’:
- Update the variable ‘CURRENT_SUM’ as ‘CURRENT_SUM’ = ‘CURRENT_SUM’ + ‘ARR[‘STARTI_NDEX’]’
- If the ‘CURRENT_SUM’ is greater than ‘TARGET’ then:
  - Update ‘MIN_LENGTH’ if ‘MIN_LENGTH’ is greater than the length of the current subarray.
  - Subtract ‘ARR[‘START_INDEX’]’ from ‘SUM’ and increment ‘START_INDEX’ by 1.
- Else:
  - Increment the value of ‘END_INDEX’ by 1.
Finally, return ‘MIN_LENGTH’.

Solve now