Last Updated: 20 Oct, 2021
Anish and subarrays!
Easy
Asked in companies
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]).
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
Approaches
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).
- Initialize a variable named MAXI with 0 to store the maximum of the subarray starting with i and ending with j.
- Iterate from i to N. (Let’s say the iterator be j).
- Update MAXI by a maximum of MAXI and ARR[j].
- If MAXI lies between X and Y, increase COUNT by 1.
- Return COUNT.
We can find out the no of sub-arrays with the ith element as its maximum. The number of sub-arrays with the ith element as its maximum will be the subarrays with starting position between i and prev[i] + 1 and ending position between i and nex[i] - 1 where prev[i] is the index of the previous greater number and nex[i] is the index of the next greater number.
Algorithm:-
- Initialize a variable named COUNT with 0 to store the number of sub-arrays.
- Initialize an array named PREV with -1 of length N.
- Initialize an array named NEX with N of length N.
- Initialize an empty STACK using a dynamic array.
- Iterate from 0 to N.(Let’s say the iterator be i).
- Start a while loop with the condition while the length of STACK is not empty.
- If the last element of the stack is less than ARR[i], pop out the last element, otherwise break.
- If STACK is not empty, update PREV[i] as the index of the last element in the STACK.
- Push ARR[i] in the STACK.
- Start a while loop with the condition while the length of STACK is not empty.
- We re-empty the stack.
- Iterate from N - 1 to 0. (Let’s say the iterator be i).
- Start a while loop with the condition while the length of STACK is not empty.
- If the last element of the stack is less than ARR[i], pop out the last element, otherwise break.
- If STACK is not empty, update NEX[i] as the index of the last element in the STACK.
- Push ARR[i] in the STACK.
- Start a while loop with the condition while the length of STACK is not empty.
- Iterate from 0 to N.(Let’s say the iterator be i).
- If ARR[i] lies between X and Y, increment COUNT by (i minus PREV[i]) * (NEX[i] minus i).
- Return COUNT.