Calculate If Duplicates Exist In An Array Using JavaScript

You’ll notice previously I did a post regarding the Fibonacci number, a popular interview question for programming jobs. To keep up with this trend of interview questions, we’re going to look into the different ways of finding duplicates in an array.

Finding array duplicates is a good question because it tests your knowledge of algorithm design and your understanding of various time complexities.

We’re going to go over two possible ways of many to accomplish this task. Both can be accomplished in just about any language, but each offers different time complexities.

Let’s look at our first possible method:

var method1 = function(a) {
    for(var i = 0; i <= a.length; i++) {
        for(var j = i; j <= a.length; j++) {
            if(i != j && a[i] == a[j]) {
                return true;
            }
        }
    }
    return false;
}

When you’re nervous in an interview, the above code may be the first thing that comes to mind. Even though it gets the job done, it doesn’t do it efficiently. Using nested loops will give you a time complexity of O(n2), which is pretty much the worst you can have.

At this point, the person interviewing you is probably going to ask you to improve upon this solution.

Let’s look at our second possible method, and my personal favorite:

var method2 = function(a) {
    var counts = [];
    for(var i = 0; i <= a.length; i++) {
        if(counts[a[i]] === undefined) {
            counts[a[i]] = 1;
        } else {
            return true;
        }
    }
    return false;
}

In the above code, we are taking in an array of values, string or integer is fine. We are then creating an empty associative array which will store the counts of each array element. If you were using Java instead of JavaScript, the associative array would be a HashMap instead. When we loop over the initial array, we use the array element value as our count key and if it doesn’t exist, we give it a value to represent it is now defined. When we hit a count key that already exists, it is because the value is a duplicate and we can immediately return true.

Because we are only using one loop, our time complexity becomes O(n), which is a significant improvement to our first method.

Conclusion

I displayed two different ways to find duplicates in an array using JavaScript. There are many other ways that might look prettier than mine. If you had a question like this in an interview or think you can top my two methods, please share your experience in the comments.

A video version of this article can be seen below.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.