Simple Queries not so simple

I got the idea of solution(finding the next and previous greater and using binary search) pretty early on. But was stuck on cases where the array was not having all unique elements. I was searching for the next greater and prev greater element due to which some of the subarrays were repeating. The trick is to find the next greater element on one side and on the other side greater element can be equal to the a[i].
i.e
a[s.top()] < a[i] for left side;
a[s.top()] <= a[i] for right side;

1 Like

How does this work? Say I have an array [300, 100, 200]. Then for 100, next and prev greater numbers are 300 and 200, so 100 will appear 60000 times?

I used the logic that in an sorted array, kth number will be max in k subarrays. But that seems to be wrong somehow.

1 Like

No, I guess you are getting this wrong. In easy language, You need to check the number of elements less than the element on left side(including element). And number of elements equal or less than the element on right side(including element).
For your array: [300,100,200]
1,3 for 300. Hence 31=3
1,1 for 100. Hence 1
1 =1
2,1 for 200. Hence 2*1=2

Taking another example:
[300,300,100,100,200,200]
for index 0: 16=6
for index 1: 1
5=5
for index 2: 12=2
for index 3: 1:1=1
for index 4: 3
2=6
for index 5: 1*1 =1

Hope this clears the doubt.

2 Likes

I couldn’t understand
for index 5: 11 =1 ?
index 2 & index 3 have value 100 which less than 200.
so it shall be at least 2
1

thanks for the clear explanation. :grin:

we are looking for contiguos sub arrays only here and in the left side we are counting elements less than the current element so for the fifth index we have one 200 and then two 100 so the counting would stop on the 200 itself and 100s would not be counted. Think about it what kind of sub arrays we want.

Click here to start solving coding interview questions