Блог пользователя AbhinavBisht

Автор AbhinavBisht, история, 2 года назад, По-английски

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
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Any link for this?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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)

»
2 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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