Follow

# Renaissance Innovation Labs

Follow # How to Return Recurring Elements in a Javascript Array With O(n) Time Complexity

Renaissance Innovation Labs
·Dec 12, 2022·

Hello there!

In this article, I’ll be showing you how to return recurring elements in a Javascript Array WIth O(n) Time complexity.

First, I’ll be showing you the wrong way to do it, then the correct way.

Let’s consider the given array;

``````const numbers = [1, 3, 2, 1, 2, 3, 4, 5, 6, 4];
``````

### METHOD 1

``````const findDuplicates = (arr) => {
const duplicates = [];
arr.forEach((number, index) => {
if (index !== arr.lastIndexOf(number)) {

duplicates.push(number);
}
});

return duplicates;
};

//findDuplicates(numbers) will return [ 1, 2, 3, 4, 6 ]
``````

In as much as this is the quickest method one can think of, under the hood has a nested loop which in turn returns an O(n)^2 time complexity.

So we move on to method 2.

### METHOD 2

In the second method, we’ll be using something called a hashMap. A hashMap is a data structure that allows us to store key-value pairs and we can use non-primitive datatype to store the data.

The Map will return the key and value pairs in the same order we inserted and it retrieves this in O(n) time-complexity.

So our second solution will look like this;

``````const findDuplicates = (arr) => {
const duplicates = [];

const map = new Map();

arr.forEach((number) => {
if (map.get(number)) {
duplicates.push(number);
} else {
map.set(number, number);
}
});

return duplicates;
};

//findDuplicates(numbers) will return [ 1, 2, 3, 4, 6 ]
``````

I do hope you’ve found this helpful, Thanks.