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

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?

• Hints: 1) you can find a median in linear time (there exists a deterministic version of QuickSelect). 2) $n + n/2 + n/4 + \cdots = O(n)$.
– user114966
Feb 14, 2021 at 10:24
• (@Dmitry I fail to make the connection from top $n$ items to top $n$ values.) Feb 14, 2021 at 11:12
• Are there a constraints about the range of values or the space used? Feb 14, 2021 at 11:22
• @greybeard, sorry, I don’t understand your question. Isn’t top n items and top n values the same thing?
– user114966
Feb 14, 2021 at 21:04
• @greybeard, I see. I understand the question as follows: for $[1,3,3,3,5]$, the answer is $[3, 3, 5]$.
– user114966
Feb 14, 2021 at 21:38

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.

• Neat! Way more elegant that the recursive solution in my answer (hinted by Dmitry). Feb 14, 2021 at 12:03

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$$.