Find the First Duplicate in a JavaScript Array

In this blog post we'll be exploring the thought process behind a solution to a potential interview question you might come across as a software engineer: how to find the first duplicate element in an array (integers, strings or otherwise.)

While this problem may be a bit more simple than something you'll directly encounter in an interview setting, the core concept we'll use to solve it (and the process of coming up with it) will be applicable to far more complex problems later on.

Ready? Let's go!

First off, let's make sure that we're clear about what our imagined prompt is:

Given an array containing integers, strings, or a mixture of data types, find the first duplicate element in the array for which the second occurrence has the minimal index. If there are more than one duplicated elements, return the element for which the second occurrence has a smaller index than the second occurrence of the other element. If there are no duplicates, return "No duplicates here!".

When you see a prompt phrased like this it can feel a bit confusing with all the talk of minimal indices, but the meat of the problem is actually quite simple when you boil it down. Essentially what's being asked is to navigate through the array, and the very first time a duplicate element is found-- that's the element to return! Describing it by minimal index is simply a more technical way of saying it, as that first duplicate should occur at an earlier/lower index in the array.

As an example, let's use this array of integers:

2, 3 and 4 are all duplicated in the array, but 3 is the first duplicate listed at an index of arr[4]. That's the one we want to return with our function!

Now, let's dig into a thought process of how to solve this. This is the key aspect of this problem, even moreso than the solution itself.

When we see a problem like this, asking for something involving duplicates in an array, whether that's finding them, eliminating them, or otherwise, we know we'll likely need two things:

1. A loop that iterates through the array.
2. A data structure that holds values for that loop to compare against.

The process here is: we know we'll need to look at most (or possibly all) of the elements of the given array-- hence the for loop-- and we'll need something to hold each of those looked-at values in order to check if we've already seen them or not. This is a logical approach that will come up in a large amount of array-related interview questions and algorithms, so it's incredibly valuable to be comfortable with.

There are various data structures that we can use to hold those values, but if we're keeping runtime complexity in mind we should limit it to, in the context of JavaScript, a hash table, Map, or Set object.

The reason we'll use one of the above here is that we'll be comparing each value of the given array to the set of already-seen elements on every pass through the loop-- checking for a key or value in a hash table is a constant time complexity, compared to using something like the Array.includes() function which adds another nested iteration on each pass. In this case we're going to use a Set object, since it functions perfectly for our particular scenario.

Time to get to work on coding our solution!

First off, let's declare our function:

 JavaScript
function firstDuplicate(arr) {

}

Now, let's create our Set object:

 JavaScript
function firstDuplicate(arr) {
   let elementSet = new Set();
}

This Set object will allow us to store each element from the given array as a unique value, and check if it already contains a value using two functions: Set.add() and Set.has().

Now, let's implement our loop through the given array:

 JavaScript
function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {

    } 
}

And finally we'll put in the core logic of our algorithm:

1. We'll check to see if the Set already contains the element that we're currently on in our loop-- if it exists, then we've found our first duplicate! We'll return that value and be done.
2. Before we can hit that milestone, we need to have an "else" statement for if the element isn't in our Set yet, in which case we add it to the Set and move on to the next element in the array.

 JavaScript
function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {
        if (elementSet.has(arr[i])) return arr[i];
        elementSet.add(arr[i]);
    } 
}

Just one final step: our edge case in which there are no duplicates to be found in the array! We'll add that after our loop, assuming that it has finished without returning a duplicate value:

 JavaScript
function firstDuplicate(arr) {
    let elementSet = new Set();

    for (let i = 0; i < arr.length; i++) {
        if (elementSet.has(arr[i])) return arr[i];
        elementSet.add(arr[i]);
    }

    return "No duplicates here!";
}

And we're done! We now have the knowledge to quickly check for and return the first duplicate in a JavaScript array, regardless of datatype. This function will return the first duplicate in an array of integers, an array of strings, or a mixed array.

Thank you for taking the time to read this tutorial, I hope you've enjoyed it and learned a bit more about the concepts behind this particular algorithm! Stay tuned for more blogs in the same vein as I work to deepen my own understanding as well. :)