Anish and subarrays!

Easy

0/40

Average time to solve is 20m

Contributed by

38 upvotes

Asked in companies

Problem statement

Anish is teaching his brother about sub-arrays. However, his brother is sometimes very inattentive. So, he wants to test whether his brother has understood the concept of sub-arrays or not. He gives his brother two numbers and asks him to find the number of sub-arrays of a certain array ARR such that the maximum element of the sub-array lies between X and Y.

Example:-

Let, 

ARR = [2, 1, 4, 3]
X = 2 , Y = 3

Answer:- 3 (The sub-arrays which meet the requirements are [2], [2, 1], [3]).

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

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

The first line of each test case contains three integers ‘N’, ‘X’, and ‘Y’ denoting the length of the array given and the two integers.

The next line of every test case contains ‘N’ integers containing the elements of the array arr.

Output Format :

For each test case, print an integer denoting the number of sub-arrays that has a maximum between X and Y.

The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 5
4 <= N <= 10^5
1 <= ARR[i] <= 10^9   
Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

6
3

Explanation for Sample Output 1 :

In the first test case, the answer should be 6 because every sub-array satisfies the conditions.
In the second test case, the answer should be 3 because the sub-arrays [2], [3], and [2, 3] satisfy the conditions.

Sample Input 2 :

1
4 1 2
4 3 6 7

Sample Output 2 :

Hint 1

Hint 2

Check every sub-array of the array.

Approaches (2)

Approach 1

Approach 2

Brute-Force

Fix the starting and ending points of the sub-array and check whether the maximum of this array lies in the range or not.

Algorithm:-

Initialize a variable named COUNT with 0 to store the number of sub-arrays.
Iterate from 0 to N.(Let’s say the iterator be i).
1. Initialize a variable named MAXI with 0 to store the maximum of the subarray starting with i and ending with j.
2. Iterate from i to N. (Let’s say the iterator be j).
  1. Update MAXI by a maximum of MAXI and ARR[j].
  2. If MAXI lies between X and Y, increase COUNT by 1.
Return COUNT.

Time Complexity

O(N ^ 2), where N is the number of points.

We are running two for loops and in each loop, we are iterating for N number of times, so the time complexity is O(N ^ 2).

Space Complexity

O(1),

Constant Space is being used.

(100% EXP penalty)

Anish and subarrays!

Console