CODEWITHSUNDEEP
javaarraylisthashset
bouncingHippo
bouncingHippo

Reputation: 6040

how do i remove duplicate elements in ArrayList in O(logn) time

I have strings as elements in the arraylist and i would like to remove them in O(logn) time, using Java

i have tried using HashSet to copy and clear and copy back to another arraylist, but i think that's in O(n) time.

Upvotes: 0

Views: 601

Answers (2)

Daniel
Daniel

Reputation: 6755

If the strings in your array are in sorted order, you can access them in O(log n) time using binary search; however, if they are unsorted, you will need to check each element of the array, giving a lower bound of O(n).

EDIT: If you are trying to remove duplicates from an already created ArrayList, you must look at each element, which will take O(n) time. If you are willing to sacrifice on adding, you can add them to the array in sorted order, and then you will never have to remove duplicates because if an element is already there, then you just don't add it; but adding will run in linear time rather than constant time.

Upvotes: 0

kan
kan

Reputation: 28951

I don't think it is possible, even if you have the array sorted it will take O(n). I think you cannot avoid checking each element at least once, so it is impossible to have complexity less than O(n).

Upvotes: 4

Related Questions