Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time

Question

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:

1. Sort the sequence and go from the top.
2. Use a modified version of quickselect.
3. 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?

Answer 1

Let $n$ denote the length of the array. We will find the largest $N$ such that there are at least $N$ elements whose value is at least $N$.

Make a pass through the array, counting the number of elements of value $1,2,\ldots,n$; if any element has value larger than $n$, count it as $n$.

Using this, determine, for each value $m \in \{1,2,\ldots,n\}$, the number of elements whose value is at least $m$.

Now you can easily determine the solution.

Answer 2

Let $S$ and $\ell$ be a set of input elements (integers) and let $\ell$ be an integer. Consider the problem of finding the maximum cardinality of a subset $S^*$ of $S$ that contains the largest elements of $S$ and suck that $\min S^* \ge |S^*| + \ell$. Your problem is captured by the special case $\ell=0$ (standard techniques allow you to find the subset $S^*$ itself, rather than just $|S^*|$).

Partition $S$ in two sets $S_1$ and $S_2$ such that $S_2 = \lfloor |S|/ 2\rfloor$ and $\forall x\in S_1, y \in S_2$, $y \ge x$. Let $m$ be the minimum element of $S_2$. $S_1$, $S_2$ and $m$ can be found in $O(|S|)$ time by finding the median $m$ of $S$, partitioning $S$ a-la-quicksort, and using some care when $S$ contains multiple copies of $x$.

If $m < |S_2| + \ell$ then the set $S_2$ contains too many elements, and you can recurse on $S_2$ and $\ell$.

If $m \ge |S_2| + \ell$ then $S_2$ is a feasible solution but is not necessarily the best one. Recurse on $S_1$ and $\ell+|S_2|$. If the value returned by the recursive call is $r$ this implies the existence of a set $S^*$ containing $r$ values from $S_1$, and all the elements in $S_2$.

The first call of the algorithm will be on $S$ and $\ell=0$.