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

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.