CODEWITHSUNDEEP
javascriptarraysperformance
James Hamann
James Hamann

Reputation: 862

I need to speed this up to pass a code fights test (javascript)

The task was to take an array and return the earliest duplicate, and if there are none return -1. I wrote it like this:

function firstDuplicate(a) {
    let singles = [];

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

        if (singles.indexOf(a[i]) == -1) {
            singles.push(a[i]);
        }
        else {
            return a[i];
        }

    }

    return -1;
}

It passed all tests except the hidden speed test. Is there another way to write this faster in JS? I saw a Java solution that used sets instead of arrays but I wanted to stick with JS.

Upvotes: 3

Views: 326

Answers (3)

Patrick Roberts
Patrick Roberts

Reputation: 51886

You can use Set in JavaScript to achieve this as well:

function firstDuplicate(array) {
  const set = new Set()

  for (const value of array) {
    if (set.has(value)) {
      return value
    }

    set.add(value)
  }

  return -1
}

console.log(firstDuplicate(['a', 1, 'b', 2, 'c', 1, 2, 3]))

The problem with your solution, as explained by @Zabuza, is your use of indexOf() which changes the time complexity of your algorithm from O(n) to O(n2), because each indexOf() is O(n).

Using Set instead Array takes advantage of hashing, which changes your lookup time by using has() for duplicates from O(n) to O(1), thus bringing the algorithm back to O(n) complexity overall.

Upvotes: 4

yBrodsky
yBrodsky

Reputation: 5041

Try this one. It should give you some more speed in the cases where there are no duplicates in a large array.

function firstDuplicate(a) {
    let singles = new Set(a);

    if(singles.size == a.length)
      return -1;

    let temp = [];


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

        if (temp.indexOf(a[i]) == -1) {
            temp.push(a[i]);
        }
        else {
            return a[i];
        }

    }
}

Upvotes: 0

pinturic
pinturic

Reputation: 2263

Instead of pushing on singles just allocate a frequency array and increase the frequency when looping through the original array. The first time the frequency is 2 you have the earliest duplicate.

Increasing by '1' the frequency at the ith element of the array is for sure faster then push on an array and then any time searching on it.

Upvotes: 0

Related Questions