6
$\begingroup$

The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers):

Given a sequence $S_\text{in}$ of $n$ integers, produce a sequence $S_\text{out}$ of elements such that any element in $S_\text{in}$ also appears in $S_\text{out}$, and all elements in $S_\text{out}$ are distinct.

Ignoring some details regarding the elements' size in bits, this can be done by sorting in $O(n \log n)$ time; or by hashing in expected time $O(n)$.

Given that we don't require $S_\text{out}$ to be sorted - is it possible to do better than sorting in the worst case?

Notes:

  • Some dependence on the output size (let's call it $m$) rather than $n$ is an improvement, but I'm mostly interested in getting closer to linearity in $n$.
  • The details I've ignored may not be so insignificant.
  • Algorithms need not be restricted to algebraic computation, i.e. you can tear into the bit representation if it helps.
  • We cannot make any assumptions regarding the input distribution.
$\endgroup$
2
  • $\begingroup$ What does $m$ stand for? $\endgroup$ Dec 1, 2018 at 2:56
  • $\begingroup$ @YuvalFilmus: See edit. I had defined it in a draft version of the question... $\endgroup$
    – einpoklum
    Dec 1, 2018 at 8:53

3 Answers 3

6
$\begingroup$

It is a classical result that the element distinctness problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\Omega(n\log n)$ time in stronger models such as algebraic decision trees, in which we are allowed to compute the sign of arbitrary bounded degree polynomials (rather than just $x_i - x_j$).

The element distinctness problem asks whether all elements in the input are distinct. This is clearly easier than your problem, since you can just compare the sizes of the input and output arrays. Hence in these computation models, you cannot do asymptotically better than $n\log n$.

$\endgroup$
3
  • $\begingroup$ Can you link to the result regarding distinctness of the comparison model? Anyway, +1 $\endgroup$
    – einpoklum
    Dec 1, 2018 at 8:52
  • $\begingroup$ Hmm. Maybe you can prove that using the fact that there are $n!$ orderings of the elements and each comparison distinguishes between 2 cases, so you need at least $\Theta(\log(n!)) = \Theta(n^n) = \Theta(n\log(n))$? $\endgroup$
    – einpoklum
    Dec 1, 2018 at 9:52
  • $\begingroup$ A web search on element distinctness should lead you to such pointers. $\endgroup$ Dec 1, 2018 at 15:54
1
$\begingroup$

You can do $O(n \log m)$ if you use a (balanced) binary search tree as a set.

I don't know about a linear-time algorithm to solve this problem, perhaps there is a reduction to prove this is impossible?

$\endgroup$
2
  • $\begingroup$ Yesh, that's a good straightforward improvement. But already that tells us we shouldn't just try to adapt the adapt the sorting lower bounds... $\endgroup$
    – einpoklum
    Jul 27, 2019 at 15:37
  • $\begingroup$ Couldn't I use a hash table with $O(m \log(m))$ entries to implement a set, and essentially get $O(n)$ for hashing plus $O(m \log(m)$ for collecting the output? $\endgroup$
    – einpoklum
    Jul 27, 2019 at 15:53
-1
$\begingroup$

If every element of the array ($a$) is in the range of $0$ to $k$, you can have $\theta(n)$ runtime when $k=O(n)$. All you have to do is to maintain an array ($c$) of $k$ elements initialized to $0$ and set $c[a[i]] = 1$ whenever $a[i]$ is encountered to be 0. At the same time you should write the corresponding element ($a[i]$) in an array $b$ only if the $c[a[i]] =0$.

$\endgroup$
7
  • $\begingroup$ This is usually written as $O(n + k)$ time. $\endgroup$
    – orlp
    Dec 1, 2018 at 0:57
  • $\begingroup$ @orlp I have mentioned if $k=O(n)$ $\endgroup$
    – Mr. Sigma.
    Dec 1, 2018 at 1:03
  • $\begingroup$ I am aware, I'm just saying that it's usually written in a different way. $\endgroup$
    – orlp
    Dec 1, 2018 at 2:01
  • 1
    $\begingroup$ Under your constraints, sorting takes $O(n)$ time (bucket sort), so you've not really improved over sorting here. $\endgroup$
    – einpoklum
    Dec 1, 2018 at 8:50
  • 1
    $\begingroup$ O(n) is faster than O(n log n). $\endgroup$
    – gnasher729
    Dec 1, 2018 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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