Given an array We need to find the count of all the elements in all the subarrays which are neither min nor max in that particular subarray
eg
4
30 47 19 23
ans = 4
i.e in 30 47 19 count is 1 --> 30 is netiher max nor min
in 30 47 19 23 count is 2 --> 30 and 23
int 47 19 23 count is 1 --> 23
3
11 20 17
ans = 1
We can have duplicate elements as input
n = 10^5 // size of array
Auto comment: topic has been updated by AbhinavBisht (previous revision, new revision, compare).
Any link for this?
Sorry , i dont have any link
Auto comment: topic has been updated by AbhinavBisht (previous revision, new revision, compare).
Consider ith element, how to find number of subarrays in which this will neither be max nor min?
Case 1: You are taking elements in subarray from both left and right side:
You can find nearest smaller item index on left(nsl) and nearest greater item index on right(ngr) and for this item to contribute you can take
(nsl+1)*(n-ngr)subarrays. Similarly, you can do for nearest smaller on right(nsr) and nearest greater on left(ngl) and add(ngl+1)*(n-nsr). But while adding both you are adding some subarrays twice which you can subtract as(min(nsl, nsr)+1)*(n-max(ngl,ngr))Case 2: You are taking elements in subarray only from right side.
To make the current element neither max nor min you'd have to go atleast till index max(nsr, ngr). So for this you would add
(n-max(nsr,ngr))Case 3: You are taking elements in subarray only from left side.
To make the current element neither max nor min you'd have to go atleast till index min(nsr, ngr). So for this you would add
min(nsl,ngl)+1UPD: You can use stack method to precompute ngl, ngr, nsl, nsr in O(N) so the final time complexity would be O(N)
Thanks , was trying the similar approach but was not able to handle all the cases.
I think this should be solvable in linear time using a cartesian tree and some maths, basically sum up all sums of subarrays, and then for each index calculate how many subarrays does the index appear as a maximum value, and subtract from the total sum.
why is this downvoted, I think this is a totally valid approach. you can just construct a cartesian tree in $$$O(n)$$$ using a stack, and then traverse the cartesian tree to subtract the max/mins for each subarray in $$$O(n)$$$ (remember to add the sum of all elements once again, because subarrays of size 1 would be subtracted twice.) did yall really try before downvoting