444iq's blog

How to find kth largest element when array is modifiable and k always vary.

By 444iq, history, 7 years ago, In English

How to find kth largest element each time where k will vary and array is modifiable. That is you can add new elements to the array array can have duplicates.

for example say array is 10 , 20 , 15.

2nd largest = 15

add 17 to array

array becomes 10 15 17 20

3rd largest = 15

Q <= 10^5.

  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

You can use PBDS

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it -7 Vote: I do not like it

    array can contain duplicates too, i tried it with pdbs but it work for unique elements.

    → Reply
    • »
      »
      »
      7 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      use less_equal instead of less.

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

        Thanks a lot. It worked.

        Suppose we also want to delete a single element which occurs more than 1 time.

        A.erase(x) will delete all x. how to erase just a single x value ?

        nilesh8757

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, hide # ^ |
           
          Vote: I like it +3 Vote: I do not like it

          You can keep pairs $$$(a_i, id)$$$ in the ordered set ($$$less$$$), where $$$id$$$ is unique for each pair.

          → Reply
»
7 years ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

Ordered_multiset

Just change less to less_equal

Like this:

#define ordered_set tree<int , null_type,less_equal<int >, rb_tree_tag,tree_order_statistics_node_update> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Try implementing it with fenwick tree. If all the values are less than 1e5 then it becomes relatively easy. If the values can go high then you need to store the queries and process the elements offline so that you can compress the higher values to smaller values.Every element will be compressed to some element <=1e5 as the no. of unique values <= 1e5. Now you can use binary search on fenwick tree !!

→ Reply