Rahul And Minimum Subarray

Moderate
0/80
16 upvotes
Asked in companies
Paytm (One97 Communications Limited)JP MorganArcesium

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 11
9 1 5 3 9
4 8
5 1 2 1
Sample Output 1:
2
4
Explanation For Sample Input 1:
In the first test case, the length of the minimum subarray is 2. The subarray is [3, 9] as the sum is 12 which is greater than the given value 11.

In the second test case, the length of the minimum subarray is 4. The subarray is [5,1, 2, 1] as the sum is 9 which is greater than the given value 8.
Sample Input 2:
2
7  32
27 1 2 4 15 12 8 
6 10
9 1 2 11 4 1
Sample Output 2:
3
1
Explanation For Sample Input 2:
In the first test case, the length of the minimum subarray is 3. The subarray is [15,12, 8] as the sum is 35 which is greater than the given value 32.

In the second test case, the length of the minimum subarray is 1. The subarray is [11] as the sum is 11 which is greater than the given value 10.
Hint

Can you think of checking the length of all the subarrays?

Approaches (2)
Brute Force

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:

 

  1. Declare a variable ‘MIN_LENGTH’ which will contain the length of the minimum subarray.
  2. 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.
  3. Finally, return ‘MIN_LENGTH’.
Time Complexity

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

 

Because there are two loops, the outer loop picks a starting element, the inner loop considers all the elements on the right side of the starting elements as the ending element. So, for every starting element, we consider all the other elements as the ending one. Hence the time complexity is O(N^2).

Space Complexity

O(1), 

 

Because we are not using any extra space for finding our answer

Code Solution
(100% EXP penalty)
Rahul And Minimum Subarray
Full screen
Console