AbhinavBisht's blog

Help me with this Ques
By AbhinavBisht, history, 2 years ago, In English

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
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AbhinavBisht (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Any link for this?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AbhinavBisht (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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)+1

UPD: You can use stack method to precompute ngl, ngr, nsl, nsr in O(N) so the final time complexity would be O(N)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks , was trying the similar approach but was not able to handle all the cases.

    → Reply
»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply