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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s