Remove duplicate elements in a array

Posted on 2006-03-26
Last Modified: 2012-08-13
How to remove duplicate elements in a array using hash tables and also without using hash tables.

this was an interview question.
Question by:tamilthambi
    LVL 45

    Accepted Solution

    All duplicates will produce the same hash value .. simply search the  hash bucket and elminate it if it is a duplicate. A good hash function will distribute the values evenly in buckets so this should be fairly fast to perform.

    Without using hash tables would depend on other constraints .. e.g. given sufficient memory you can allocate an array of range of value in that array .. simply keep marking the index value equal to data value and  consolidate the values in single scan ... This would bebad if range is huge but number of values is small ....
    Or you can try sorting the array ... Or try to construct a binary search tree .. basically you need to gauge what is that interviewer is trying to have you optimize .. ask him/her questions to determine the constraints/performance they are looking for.

    LVL 24

    Assisted Solution

    without hash you can sort the array. Then you walk it and you copy all the unique elements to another array. You even can keep the same array you just have to remove the not unique elements, e.g while setting the to a known value which indicates it "not there".

    The problem with hashes is that you can get the same hash for different values. That happens sooner or later, so you can not eliminate it that easy. The only way not to let happen if you can assure that no element in the field yields the same hash code.

    So sunnycoder is not fully right on his first suggestion.

    LVL 45

    Expert Comment


    Perhaps I was not clear enough. I never said that two different values cannot produce same hash. What I said was duplicate values will have the same hash (unless ofcourse you are using some hash function like time()%value). That was the reason I said you need to search the hash bucket before eliminating an element.


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Top 6 Sources for Identifying Threat Actor TTPs

    Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

    An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
    Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode ( They will have you believe that Unicode requires you to use…
    The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
    Video by: Grant
    The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

    761 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    7 Experts available now in Live!

    Get 1:1 Help Now