<p>Not possible in a comparison based setting. You can easily reduce the problem of finding repeated elements to uniqueing. Since the former has a lower bound of $n \log n$ by <a href="http://www.ecommons.cornell.edu/bitstream/1813/6345/1/82-505.pdf" rel="nofollow">Misra &amp; Gries '82</a>, it ain't gonna happen. There may be solutions that exploit the fact that you are using integers, but my intuition says this isn't true.</p>

<p><strong>Edit</strong>: sorry, I meant that I didn't think there was <em>linear time</em> algorithm for uniqueing integers (in the general case). There is clearly a $o(n \log n)$ algorithm for uniqueing integers by Han's integer sorting routine. I could have sworn linear time was mentioned in the question, but I guess it wasn't.</p>

CC BY-SA 3.0
2011-05-29T08:49:13.620Z
Actually, the following papers improved Misra and Gries to $O(n)$: Demaine ED, L ́opez-Ortiz A, Munro JI. Frequency estimation of internet packet streams with limited
space. ESA, 2002; 348–360    and    Karp RM, Shenker S, Papadimitriou CH. A simple algorithm for finding frequent elements in streams and
bags. ACM Trans. Database Syst. 2003; 28(1):51–55, doi:http://doi.acm.org/10.1145/762471.762473.        They use better data structures to achieve this upper bound.
Massimo Cafaro
CC BY-SA 3.0
2011-05-29T16:32:46.423Z
You can't "improve" a lower bound from $n \log n$ to $n$. They are either operating under different assumptions or the first paper was erroneous. Considering that the first paper is highly cited, I doubt the latter.
Christopher Monsanto
CC BY-SA 3.0
2011-05-29T16:39:35.837Z
(Just read the last paper) their results are amortized, not worst case.
Christopher Monsanto
CC BY-SA 3.0
2011-05-29T17:06:39.497Z
The paper from Demaine provides a worst case result, the one from Karp uses hashing and therefore provides an average case result (even though it can easily be improved to worst case using Cuckoo hashing instead of traditional hashing). The paper from Misra and Gries achieves $O(n \log n)$ using an AVL tree. Demaine uses a much smarter data structure to achieve $O(n)$: as discussed by Demain itself (see http://erikdemaine.org/papers/NetworkStats_ESA2002/), his deterministic algorithm is identical to the one of Misra and Gries, except for the data structure used.
Massimo Cafaro
CC BY-SA 3.0
2011-05-29T17:23:57.913Z
Again, you can't have an $O(n)$ algorithm for a $\Omega(n \log n)$ problem. I skimmed one of your papers to find the difference in assumptions, I invite you to find the difference in the other paper.
Christopher Monsanto
CC BY-SA 3.0
2011-05-29T18:42:48.703Z
Christopher, I have actually read both of them, because I have just published a parallel version of the Frequent algorithm due to Demaine. Both basically delete k-uples of distinct elements, exactly as in Misra and Gries. Again, the only difference I have spotted is in the use of a smarter data structure. But, if I am wrong about this, I would be interested to know what exactly is wrong, since I am continuing working on this problem (from a parallel perspective).
Massimo Cafaro
CC BY-SA 3.0
2011-05-29T18:48:42.600Z
The lower bound isn't for the *algorithm*, it is for the problem -- in other words, over all data structures and algorithms. Both papers are "right", but they necessarily must operate under different assumptions (perhaps preprocessing? additional structure in the input?)
Christopher Monsanto
CC BY-SA 3.0
2011-05-29T18:49:43.880Z
Also, you mention that one can improve the average case to worst case by using Cuckoo hashing. As far as I know, Cuckoo hashing will give you worst case constant deletion and lookup, but insertion is still amortized, which doesn't give you a worst case bound on the algorithm as a whole.
Christopher Monsanto
CC BY-SA 3.0
2011-05-29T19:24:21.290Z
I fully understand that a lower bound applies to a problem, not a specific algorithm ;-) However, having said that, I still can not find any difference: all of these algorithms (Misra-Gries, Demaine and Karp) do basically the same operation. They delete k distinct elements until this operation is no longer possible (n/k times). The only difference to me is that they use a different data structure to accomplish this goal. May be I am wrong, but if I am wrong I would be interested to know why, since I am still working on the same topic even though from a parallel perspective.
Massimo Cafaro
CC BY-SA 3.0
2011-05-29T19:25:56.967Z
About Cuckoo hashing: you are right, insertion performance is still given in the average case.
Massimo Cafaro
CC BY-SA 3.0
2011-05-29T19:45:59.577Z
The Ω(n log n) lower bound for element distinctness (Are these n integers all different?) holds in the average case as well as the worst case, in various decision tree models.  That's not the issue.
Jeffε
CC BY-SA 3.0
2011-05-29T23:25:27.633Z
@Christopher, as Jeff E. points out in another comment, if the Karp paper uses hashing, the lower bound against bounded degree decision trees does not really hold. Also, I don't see how there is any issue of amortized time here: you have a static array, you need to "unique it"; what do you amortize over? Furthermore, I don't see how this lower bound gives any intuition into uniqueing integers. The problem is in linear time (and $O(1)$ space) for well-bounded integers and $o(n \log n)$ for general integers. The lower bound gives no reason to believe $O(n)$ cannot be achieved in general.
Sasho Nikolov
CC BY-SA 3.0
2011-05-30T03:14:08.303Z
The whole point of this argument is that @unforgiven said that the hashing paper "improved" the lower bound given by Misha & Gries. I have said over and over that the two papers operate under different assumptions. I do not understand why you are addressing me to reiterate what I have been saying all along.
Christopher Monsanto
CC BY-SA 3.0
2011-05-30T03:17:21.577Z
To address your second point, I never claimed the $O(n \log n)$ lower bound provided any insight into uniqueing integers. I don't think $O(n)$ can be achieved because we haven't seen anything in that ballpark for sorting integers in the general case.
Christopher Monsanto
CC BY-SA 3.0
2011-05-27T16:37:22.610Z
2011-05-29T01:23:32.077Z
2011-05-29T01:23:32.077Z
Christopher Monsanto
<p>In practice you can solve this problem easily in linear expected time with a hash table: just hash everything and eliminate the duplicates when they collide with each other. See, e.g. <a href="http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/" rel="nofollow">this Python recipe</a> which primarily uses hashing but falls back on other strategies for objects that can't be hashed.</p>

<p>Whether you accept this as an acceptable theoretical answer depends somewhat on your model of computation.</p>

CC BY-SA 3.0
2011-05-29T02:22:49.880Z
See: my first comment on the problem? ;)
Christopher Monsanto
CC BY-SA 3.0
2011-05-29T06:07:04.783Z
Well, yes, but it deserves to be an answer not just a comment. I've just set it to be CW, which if I understand correctly means that I don't get undeserved credit when people vote for it.
David Eppstein
CC BY-SA 3.0
2011-05-29T19:44:55.553Z
The O(n) upper bound doesn't contradict the Ω(n log n) lower bound; it just requires a different model of computation. Misra and Gries's Ω(n log n) lower bound holds in the comparison tree model, and more generally in the algebraic decision tree and algebraic computation tree models [Steele and Yao, Ben-Or].  These models all *define* an algorithm as a family of binary or ternary decision trees.  Hashing and radix sort violate this assumption; the code A[i]=hash(x) is making a multi-way decision based on the value of hash(x).
Jeffε
CC BY-SA 3.0
2011-05-29T20:47:57.847Z
@JeffE, is anyone arguing the opposite?
Christopher Monsanto
CC BY-SA 3.0
2011-05-29T01:43:37.133Z
2011-05-29T01:43:37.133Z
David Eppstein
<p>On the other hand there exists a relatively simple linear-time algorithm for well-bounded integers. The algorithm that does do more than compare elements: it uses bit manipulations and radix sort.</p>

<p>If $a_i$ are polynomially bounded, then there exists an in-place version of radix sort that works in $O(n)$ time: <a href="http://www.cs.rutgers.edu/~muthu/soradix.pdf" rel="nofollow">FMP</a>. They have various improvements (stability, etc.), but the basic idea is easy to describe. First you sort the first $n/\log n$ numbers using in-place mergesort in time $O(n)$. Then, the sorted integers can be compressed to free-up $\Omega(n)$ bits: the intuitive reason for this is that the binary entropy of sorted sequences is smaller than the entropy of arbitrary sequences. The details of how to do the compression in-place in linear time are not very hard: the technique is an extension of the idea that in a sorted array you can remove the most significant bit of every integer and just remember the index of the smallest integer that has a most significant bit 1. That's not quite enough, but they can remove the most significant $\log (n/3)$ bits, and that gives enough savings.</p>

<p>The next step is the obvious thing: use the usual radix sort with the freed-up space to sort the remainder of the array.</p>

CC BY-SA 3.0
2011-05-27T18:25:42.667Z
2011-05-27T19:55:29.513Z
2011-05-27T19:55:29.513Z
Sasho Nikolov
<p>let $A = [ a_1 \dots a_n ]$ be a <em>sorted</em> list of integers of length $n$. By a simple algorithm that works in-place and in linear time we can remove all duplicates and output a sorted list of unique integers that are precisely the integers which appear .</p>

<p>More generally, it suffices to have a list with the promise that all identical integers are merely grouped to apply the same idea.</p>

<p>Now let $A$ be a list of integers, neither sorted nor even grouped as above. Let us call the problem of outputting a not-necessesarily sorted list of integers that are precisely the integers appearing $A$ by the term "uniquing problem".</p>

<p>An algorithm to solve the "uniqueing problem" might sort the list and remove multiple entries in the obvious way, thus requireing a running time of O( n log(n) ). Can we do better? I don't think so, although there might be a speed up because we actually do not require any sorting on the output list, so this algorithm performs actually too much.</p>

<p>Best, 
Martin</p>

CC BY-SA 3.0
2011-05-27T16:08:44.747Z
I assume you either mean non-amortized linear time or in constant space, or else a simple algorithm that records what it has seen in a hash table would solve this problem in linear time.
Christopher Monsanto
CC BY-SA 3.0
2011-05-28T07:23:57.243Z
i am puzzled why an answer that gives a lower bound in a weak computational model was accepted given that there exists an algorithm that beats the lower bound in a general model. $n$ integers can be sorted in-place (which solves the "uniqueing problem") in $o(n \log n)$ time even when the integers are not polynomially bounded: check the link I gave
Sasho Nikolov
CC BY-SA 3.0
2011-05-29T01:24:54.850Z
Perhaps Martin actually wanted to know if one could identify unique elements of arbitrary type, but mentioned integers for the sake of being concrete?
Christopher Monsanto
<ds.algorithms>
'Uniqueing' an unsorted list of integers
shuhalo
# 'Uniqueing' an unsorted list of integers

(Asked by: username_0 on 2011-05-27)

let $A = [ a\_1 \dots a\_n ]$ be a *sorted* list of integers of length $n$. By a simple algorithm that works in-place and in linear time we can remove all duplicates and output a sorted list of unique integers that are precisely the integers which appear .

More generally, it suffices to have a list with the promise that all identical integers are merely grouped to apply the same idea.

Now let $A$ be a list of integers, neither sorted nor even grouped as above. Let us call the problem of outputting a not-necessesarily sorted list of integers that are precisely the integers appearing $A$ by the term "uniquing problem".

An algorithm to solve the "uniqueing problem" might sort the list and remove multiple entries in the obvious way, thus requireing a running time of O( n log(n) ). Can we do better? I don't think so, although there might be a speed up because we actually do not require any sorting on the output list, so this algorithm performs actually too much.

Best,
Martin

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: I assume you either mean non-amortized linear time or in constant space, or else a simple algorithm that records what it has seen in a hash table would solve this problem in linear time.  
> **username_2**: i am puzzled why an answer that gives a lower bound in a weak computational model was accepted given that there exists an algorithm that beats the lower bound in a general model. $n$ integers can be sorted in-place (which solves the "uniqueing problem") in $o(n \log n)$ time even when the integers are not polynomially bounded: check the link I gave  
> **username_1**: Perhaps Martin actually wanted to know if one could identify unique elements of arbitrary type, but mentioned integers for the sake of being concrete?  

---

## 3 answers

### Answer by username_1 on 2011-05-27. Score: 2 | Accepted answer

Not possible in a comparison based setting. You can easily reduce the problem of finding repeated elements to uniqueing. Since the former has a lower bound of $n \log n$ by [Misra & Gries '82](http://www.ecommons.cornell.edu/bitstream/1813/6345/1/82-505.pdf), it ain't gonna happen. There may be solutions that exploit the fact that you are using integers, but my intuition says this isn't true.

**Edit**: sorry, I meant that I didn't think there was *linear time* algorithm for uniqueing integers (in the general case). There is clearly a $o(n \log n)$ algorithm for uniqueing integers by Han's integer sorting routine. I could have sworn linear time was mentioned in the question, but I guess it wasn't.

> **Comments:**
> **username_3**: Actually, the following papers improved Misra and Gries to $O(n)$: Demaine ED, L ́opez-Ortiz A, Munro JI. Frequency estimation of internet packet streams with limited space. ESA, 2002; 348–360    and    Karp RM, Shenker S, Papadimitriou CH. A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 2003; 28(1):51–55, doi:http://doi.acm.org/10.1145/762471.762473.        They use better data structures to achieve this upper bound.  
> **username_1**: You can't "improve" a lower bound from $n \log n$ to $n$. They are either operating under different assumptions or the first paper was erroneous. Considering that the first paper is highly cited, I doubt the latter.  
> **username_1**: (Just read the last paper) their results are amortized, not worst case.  
> **username_3**: The paper from Demaine provides a worst case result, the one from Karp uses hashing and therefore provides an average case result (even though it can easily be improved to worst case using Cuckoo hashing instead of traditional hashing). The paper from Misra and Gries achieves $O(n \log n)$ using an AVL tree. Demaine uses a much smarter data structure to achieve $O(n)$: as discussed by Demain itself (see http://erikdemaine.org/papers/NetworkStats_ESA2002/), his deterministic algorithm is identical to the one of Misra and Gries, except for the data structure used.  
> **username_1**: Again, you can't have an $O(n)$ algorithm for a $\Omega(n \log n)$ problem. I skimmed one of your papers to find the difference in assumptions, I invite you to find the difference in the other paper.  
> **username_3**: Christopher, I have actually read both of them, because I have just published a parallel version of the Frequent algorithm due to Demaine. Both basically delete k-uples of distinct elements, exactly as in Misra and Gries. Again, the only difference I have spotted is in the use of a smarter data structure. But, if I am wrong about this, I would be interested to know what exactly is wrong, since I am continuing working on this problem (from a parallel perspective).  
> **username_1**: The lower bound isn't for the *algorithm*, it is for the problem -- in other words, over all data structures and algorithms. Both papers are "right", but they necessarily must operate under different assumptions (perhaps preprocessing? additional structure in the input?)  
> **username_1**: Also, you mention that one can improve the average case to worst case by using Cuckoo hashing. As far as I know, Cuckoo hashing will give you worst case constant deletion and lookup, but insertion is still amortized, which doesn't give you a worst case bound on the algorithm as a whole.  
> **username_3**: I fully understand that a lower bound applies to a problem, not a specific algorithm ;-) However, having said that, I still can not find any difference: all of these algorithms (Misra-Gries, Demaine and Karp) do basically the same operation. They delete k distinct elements until this operation is no longer possible (n/k times). The only difference to me is that they use a different data structure to accomplish this goal. May be I am wrong, but if I am wrong I would be interested to know why, since I am still working on the same topic even though from a parallel perspective.  
> **username_3**: About Cuckoo hashing: you are right, insertion performance is still given in the average case.  
> **username_4**: The Ω(n log n) lower bound for element distinctness (Are these n integers all different?) holds in the average case as well as the worst case, in various decision tree models.  That's not the issue.  
> **username_2**: @Christopher, as Jeff E. points out in another comment, if the Karp paper uses hashing, the lower bound against bounded degree decision trees does not really hold. Also, I don't see how there is any issue of amortized time here: you have a static array, you need to "unique it"; what do you amortize over? Furthermore, I don't see how this lower bound gives any intuition into uniqueing integers. The problem is in linear time (and $O(1)$ space) for well-bounded integers and $o(n \log n)$ for general integers. The lower bound gives no reason to believe $O(n)$ cannot be achieved in general.  
> **username_1**: The whole point of this argument is that @unforgiven said that the hashing paper "improved" the lower bound given by Misha & Gries. I have said over and over that the two papers operate under different assumptions. I do not understand why you are addressing me to reiterate what I have been saying all along.  
> **username_1**: To address your second point, I never claimed the $O(n \log n)$ lower bound provided any insight into uniqueing integers. I don't think $O(n)$ can be achieved because we haven't seen anything in that ballpark for sorting integers in the general case.  

---

### Answer by username_5 on 2011-05-29. Score: 7

In practice you can solve this problem easily in linear expected time with a hash table: just hash everything and eliminate the duplicates when they collide with each other. See, e.g. [this Python recipe](http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/) which primarily uses hashing but falls back on other strategies for objects that can't be hashed.

Whether you accept this as an acceptable theoretical answer depends somewhat on your model of computation.

> **Comments:**
> **username_1**: See: my first comment on the problem? ;)  
> **username_5**: Well, yes, but it deserves to be an answer not just a comment. I've just set it to be CW, which if I understand correctly means that I don't get undeserved credit when people vote for it.  
> **username_4**: The O(n) upper bound doesn't contradict the Ω(n log n) lower bound; it just requires a different model of computation. Misra and Gries's Ω(n log n) lower bound holds in the comparison tree model, and more generally in the algebraic decision tree and algebraic computation tree models [Steele and Yao, Ben-Or].  These models all *define* an algorithm as a family of binary or ternary decision trees.  Hashing and radix sort violate this assumption; the code A[i]=hash(x) is making a multi-way decision based on the value of hash(x).  
> **username_1**: @JeffE, is anyone arguing the opposite?  

---

### Answer by username_2 on 2011-05-27. Score: 3

On the other hand there exists a relatively simple linear-time algorithm for well-bounded integers. The algorithm that does do more than compare elements: it uses bit manipulations and radix sort.

If $a\_i$ are polynomially bounded, then there exists an in-place version of radix sort that works in $O(n)$ time: [FMP](http://www.cs.rutgers.edu/~muthu/soradix.pdf). They have various improvements (stability, etc.), but the basic idea is easy to describe. First you sort the first $n/\log n$ numbers using in-place mergesort in time $O(n)$. Then, the sorted integers can be compressed to free-up $\Omega(n)$ bits: the intuitive reason for this is that the binary entropy of sorted sequences is smaller than the entropy of arbitrary sequences. The details of how to do the compression in-place in linear time are not very hard: the technique is an extension of the idea that in a sorted array you can remove the most significant bit of every integer and just remember the index of the smallest integer that has a most significant bit 1. That's not quite enough, but they can remove the most significant $\log (n/3)$ bits, and that gives enough savings.

The next step is the obvious thing: use the usual radix sort with the freed-up space to sort the remainder of the array.


---

