Editorial Fitness Freak Coyote

Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote

In this question there are two types of query.

1. Add number in your data structure
2. Return number whose rank is floor of n/3

And both query come at any instance of time.

So we can use Balanced Binary Search Tree. But that take O(log n) time complexity in both query.

The better approach is use two heaps.

Create a min heap of size n/3 and create max heap of size 2n/3

So for the second query we give minimum element from the min heap whose rank is floor of n/3

which takes time O(1).

For the first query there can be four cases occur.

-If size of min heap is less than floor of n/3 this is due to increase in n.

in this case we will add that number in the min heap and than compare min of min heap and max of max heap

If max of max heap is greater than min of min heap than we will swap this two elements.

-If size of min heap is equal to floor of n/3

In this case just add it in the max heap.

So the time complexity of this is  O(log n)

Java implementation code

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote/submissions/code/3618642