ProgrammingNode JS

Typescript – Finding Duplicate Elements in an Array

How to find all duplicate elements in an array from a specific property

Have you ever wanted to find some duplicate elements in an array? Lets take a look at how to do just that in Typescript. (Note, this is similar to Array.prototype.filter(), however, I wanted to write this with strict typing.

Stack Overflow has a good start to this problem and comes up with this answer. However that was only a JavaScript version, and only check to see if there is one instance in the array, not returning all duplicate elements.

Plain Example

Before we get into generics and types, lets have a look at the implementation we want to make type-safe. It’s a simple for loop, where if the property of each element is equal to our value, then push it to an array of ‘found elements’. Then return that new list.

private findElements(array, property, value){
	let foundElements = [];
	
	for(let element of array) {
		if(element[property] === value) {
			foundElements.push(element);
		}
	}
	
	return foundElements;
}

This is a great start, but to solve this in Typescript, we need to use something called generics. Found in most strictly typed languages, it is a way of passing a description of an object at a later time. In short, it’s like extra re-usable code. Which is always good right?

Implementing in Typescript

If you’re not familiar with generics, you may want to read on them before continuing. I’ll write a post on this soon and paste a link here.

private findElements<T, V>(array: T[], property: string, value: V): T[] {
	let foundElements: T[] = [];
	for(let element of array) {
		if(element[property] === value) {
			foundElements.push(element);
		}
	}
	return foundElements;
}

As you can see from the code above, we start by creating a new array of found elements, which has the array type of T. Then we loop through the array passed into the function which has the same type (very important).

Next we check the element’s dynamic property in square brackets. For example:

return array.name;
// is the same as
return array['name'];

// which is the same as
let property = 'name';
return array[property];

The type of the value parameter is mapped to the type V passed in as a generic.

Creating types and calling this function would work like this:

type Person = {name: string, age: number};
let people: Person[] = [];

people.push({name: 'john', age: 35});
people.push({name: 'debby', age: 29});
people.push({name: 'smith', age: 44});

let duplicates = this.findElements<Person, number>(people, 'age', 44);

I’m creating a temporary type here called person, which is an object containing a name, of type string and age, of type number. Then creating a new array called people, which is an array of type Person. Next we push a few elements into the array, just for testing.

Now we call the findElements function and pass to it; the type of array, type of property we’re checking against, the array to loop through, the property accessor and the value we want to compare to determine if it’s a duplicate. When the new array of duplicates is returned, it will have the same time as the array you passed in. which is awesome!

Performance Improvement

For of loops (documentation here) are actually quite slow. To show you just how slow they are in the browser, here’s a quick example of the difference between checking through a simple array with a standard loop vs the for of approach.

js-perf-let-of-vs-var-loop
jsPerf performance test of for let of vs standard var loop

As you can see, it is far faster to loop through manually, so lets adjust our function accordingly.

private static findElements<T, V>(array: T[], property: string, value: V): T[] {
    let foundElements: T[] = [];
    for(var i: number = 0, len: number = array.length; i < len; i++) {
        if(array[i][property] === value) {
            foundElements.push(array[i]);
        }
    }
    return foundElements;
}

This VS Array.Filter

I was curious to see how our own implementation of finding duplicates in an array would compare to array.filter in terms of performance. Below is a quick jsPerf example. (I didn’t test all browsers, just Chrome).

It’s also worth noting that array.filter has more functionality than just checking for duplicates. It also allows filtering on logical operators such as integers that are greater / less than, properties having a length greater / less than etc.

jsPerf performance test array.filter vs our custom function
jsPerf performance test array.filter vs our custom function

If you’re wondering why there’s two code cases for the array.filter. That’s because I was curious to see what performance hit using two equals instead of three would have on a higher order function. MDN web docs have a good explanation about equality comparisons and sameness.

That just about wraps it up for this post on how to find duplicate elements with Typescript and optimising the performance. If you have any questions or improvement suggestions, please feel free to drop a comment.

Tags

Nicholas Mordecai

Just your friendly neighbourhood programmer!

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Close
Close