I have used a **TreeSet** which is basically an in-built implementation of **red-black tree**

And its also given in its java documentation, that all **add,remove operations** take **log(n) time**

Then for the **Kth and Count Queries** ,i am **converting** the **Treeset object** into an **array** and doing a **binary search** over the array.

So basically all operations take just **log(n)** time.

So why TLE??

Also the ideone test case answer is correct…i have confirmed it from an accepted solution.

Well, isn’t converting a TreeSet into an Array an O(n) operation?

1 Like

Also, it would be nice if anyone can explain the segment tree and fenwick tree approach…

Ohh, i missed that. Thank you so much.

Can you explain the segment tree and fenwick tree approach?

First you normalise all numbers you find in the input, then you keep a segment tree on a 0-1 vector of every number’s apparencies. Three of the operations are trivial on this data structure, for the kth-order statistic you can either use binary search, for a total of O(log^2) per query, or think of a clever aproach which gives O(log) per query. Hope this helped.