Search code examples
javadata-structurestailhead

Data structure with logarithmic insert/delete and "no-greater-than"

I'm solving a coding challenge right now, and I have a solution, but for it to work, I need a data structure which supports four operations:

  • Insertion in O(log(N))
  • Deletion in O(log(N))
  • Checking how many elements are greater than a specified element in O(log(N))
  • Checking how many elements are less than a specified element in O(log(N))

I tried solving it using Java's TreeSet which can support these operations by add, remove, headSet and tailSet (and checking the size of the two last ones). But this solution is too slow. I haven't checked the time complexities but I have a feeling that ...set do not run in logarithmic time (or run inefficiently).

Does anyone know of a data structure I can implement to support these operations? Is it even possible? And, if it is in some tree shape, preferably self-balancing?

Solution

  • As mentioned in the comments above, "Order statistic trees" solved the problem I asked for elegantly, and in addition, were relatively easy to implement, and ultimately gave me an accepted submission for the challenge. Thanks!