Recently one of my friend's was asked this question int Google's screening round:

If you have an array of size N which is sorted in a non-decreasing manner and has duplicates. You have to delete k largest elements from it and then tell us the size of the remaining array. So suppose the array is :

[1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 5] and k = 2;

After removal it will become :
[1, 1, 1, 2, 3, 3, 3] and the size is : 7

The O(n) solution is pretty straight forward just do the deduplicatin wwhile counting from backward.

I was also able to come up with a O(klog(N)) solution by basically picking up elemnts from the last and finding out their first occurence then picking the next lower number till we have picked k elements and then the first occurence of that will represent the reduced size. But this solution only works if k << N. Otherwise the complexity comes to around O(NlogN) itself which is worse than O(N).

I was wondering if there is a better solution of this problem possible.

Note: Array might not have consecutive elements

TIA