DEV Community

Cover image for Find the First Duplicate in a JavaScript Array
Sean Welsh Brown
Sean Welsh Brown

Posted on

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:

Alt Text

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:

function firstDuplicate(arr) {

}

Now, let's create our Set object:

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:

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.
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:

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. :)

Top comments (5)

Collapse
 
djamaile profile image
Djamaile

Follow up would be to do this in constant space where the complexity doesn’t exceed O(n*2). For that you can use the Floyd’s Turtoise and Hare algorithm.

Collapse
 
seanwelshbrown profile image
Sean Welsh Brown

Thanks for the suggestion! I'm trying to learn more about space/time complexity as I go along, so I really appreciate the nod for a direction to look in.

Collapse
 
danieldawson profile image
Daniel Dawson

Sorry, I just don't see how that algorithm helps us in this case. I've only used that to solve problems with cycles, and couldn't find any information as to how the Tortoise and Hare algorithm helps us solve this problem.

If you could post your source or a sample solution, I would appreciate it.

Collapse
 
djamaile profile image
Djamaile

You’re right, i misread the question. I recently had this question during my FAANG phone interview, i eventually ended up using binary search. Then he went on about turtle and hare, bla bla. Luckily he deemed it not really important to know, but a other interviewer might not be that nice.

This was the question btw: leetcode.com/problems/find-the-dup...

Collapse
 
petrasp profile image
Petra Spirkova • Edited

The most comprehensive explanation of the algorithm i've seen so far. Thanks a lot Sean!
The space complexity can indeed be further improved (end of this video: https://www.youtube.com/watch?v=XSdr_O-XVRQ&ab_channel=NickWhite)
const findFirstDuplicate = list => {
for (let i = 0; i < list.length; i++) {
if (list[Math.abs(list[i]) - 1] < 0) {
return Math.abs(list[i]);
} else {
list[Math.abs(list[i]) - 1] = -list[Math.abs(list[i]) - 1];
}
}
return -1;
};