### PROBLEM LINKS:

### DIFFICULTY:

Easy

### PREREQUISITES:

Heaps

### PROBLEM:

You’re given an online stream of numbers. At any point of time if **K** numbers have already appeared, you need to find out **floor(K/3)**^{th} largest number.

### QUICK EXPLANATION:

Maintain two heaps - one min heap for top **floor(K/3)** numbers and other max heap for all remaining numbers.

### DETAILED EXPLANATION:

We can maintain two different heaps - one min heap for top **1/3 ^{th}** of votes and

one max heap for all other votes. Once we have this, we can simulate actual

voting itself. The reason is after every vote, at maximum 1 vote moves between

the heaps.

To understand this, let’s say that at some point of time we’ve **x** votes in top heap

and **N - x** votes in other heap. If a new vote comes push it in one of the two halves

by comparing its value to the lowest value in top heap. Now assume it went in top

heap. Number of votes in top heap might be more than **floor( (N+1) / 3)** now in which case we’d need to transfer some numbers to the other heap. But difference

is only of 1 vote as number of votes in top heap <= **1 + floor(N/3)** and hence only 1 vote needs

to goto bottom heap. That one vote has to be the minimum value of this heap.

By similar argument, had the vote gone to bottom heap, again only its topmost value

need to be transfered to top heap, if at all.

At any query, all we have to do is find out the smallest value from top heap and print it.

Complexity of our solution is **O(N log N)** as we take **O(log N)** time per query.

### SETTER’S SOLUTION:

Can be found here.

### TESTER’S SOLUTION:

Can be found here.