1
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – user114966
    Feb 14, 2021 at 10:24
  • $\begingroup$ (@Dmitry I fail to make the connection from top $n$ items to top $n$ values.) $\endgroup$
    – greybeard
    Feb 14, 2021 at 11:12
  • $\begingroup$ Are there a constraints about the range of values or the space used? $\endgroup$
    – greybeard
    Feb 14, 2021 at 11:22
  • $\begingroup$ @greybeard, sorry, I don’t understand your question. Isn’t top n items and top n values the same thing? $\endgroup$
    – user114966
    Feb 14, 2021 at 21:04
  • 1
    $\begingroup$ @greybeard, I see. I understand the question as follows: for $[1,3,3,3,5]$, the answer is $[3, 3, 5]$. $\endgroup$
    – user114966
    Feb 14, 2021 at 21:38

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Neat! Way more elegant that the recursive solution in my answer (hinted by Dmitry). $\endgroup$
    – Steven
    Feb 14, 2021 at 12:03
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.