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.

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

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

1 Like

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.