how to remove duplicates from an array without sorting

Question

Hello, i have an array which might contain duplicate objects. I wonder if it's possible to find and remove the duplicates in the array: - without sorting (strict requirement) - without using a temporary secondary array - possibily in O(N), with N the nb of the elements in the array

In my case the array is a Lua array, which contains tables:

t={
{a,1},
 {a,2},
 {b,1},
 {b,3},
 {a,2}
} 

In my case, t[5] is a duplicate of t[2], while t[1] is not.

Answer 1

Iterate the array, stick every value in a hash, checking if the it exists first. If it does remove from original array (or don't write to the new one). Not very memory efficient, but only 0(n) since you are only iterating the array once.

Answer 2

Can't be done in O(n) but ...

what you can do is

• Iterate thru the array
• For each member search forward for repetitions, remove those.

Worst case scenario complexity is O(n^2)

Answer 3

To summarize, you have the following options:

• time: O(n^2), no extra memory - for each element in the array look for an equal one linearly
• time: O(n*log n), no extra memory - sort first, walk over the array linearly after
• time: O(n), memory: O(n) - use a lookup table (edit: that's probably not an option as tables cannot be keys in other tables as far as I remember)

Pick one. There's no way to do what you want in O(n) time with no extra memory.