striker_46's blog

Count of max element

By striker_46, history, 9 months ago, In English

How to find number of elements greater than that elements for all elements of the array on the right side.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use policy based data structure ( Ordered set ) . Then you can traverse the array from the right and keep checking no. of elements using order_of_key(a[i]) . o(nlogn) tc

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

    I guess ordered set not work in case of duplicate element.

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

      It works

      4 types of modification you can do Greater Greater Equal Less Less Equal

      typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    op_set;

It acts like ordered-multiset , if you remove equal it acts like normal set
      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Also ig it can be done using Divide and conquer ( Merge sort )

Here similar problem on leetcode :

https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also use Segment Tree, if array value is large in that case you have to normalize it down to <=n range.

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

    Can you explain more as I am not much familiar with segment tree.

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

you can sort the array in decreasing order keeping their index then you build segment / fenwick tree ans for index i is i — sum(0..j) j denotes index of element in original array then update the value of segment / fenwick tree. sum(0..i) denotes cnt of elements having value less <= element at index i and index < j

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Caculate i < j and a_i < a_j. Enumerate from n to 1. For position i, you only need to caculate how many greater than a_i. Use BIT, query(n) — query(a[i]) is answer for position i.

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

    Also, you should normalize a[i] to the range [1,n]

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

    Can you please explain this in a bit more detail and with clarity? Also what is the time complexity of this approach?

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i guess find the next greater element for every element to its right and add 1 to the answer* of that element to get the answer for this element.

  • answer means-- number of elements to its right such that they are greater than this element
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess you are trying to find count of inversions in array which is

if i < j and a[i] > a[j]

This can be done using merge sort along with a simple modification.

Link to understand sol

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Statement's really unclear, can you clarify what the problem is?

→ Reply