I am looking for a solution for the following problem:
Find the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time.
Consider the following sequence: $$ 3, 1, 6, 1, 5 $$ The answer here is $3$, with $6, 5, 3$ being in the set found. The value of $N$ is not a given - we're looking for the largest $N$.
So far, I came up with three solutions:
- Sort the sequence and go from the top.
- Use a modified version of quickselect.
- Use a modified version of BST where elements bigger than the current $n$ are inserted, and elements smaller than the new $N$ are removed.
1 and 3 are more or less $n\log n$ (though I'd expect 3 to be faster), 2 is best case $n$, worst case $n^2$.
Our teacher told us it's possible to do it in a reliable $n$ time. What is the algorithm for the linear solution, if there's one?