I need to speed this up to pass the fights test with code (javascript)
The challenge was to take the array and return the earliest duplicate, and if no 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 any other way to write this faster in JS? I saw a Java solution that used many instead of arrays, but I wanted to stick with JS.
source to share
You can use Set
in JavaScript for this:
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 to use indexOf()
that changes the time complexity of your algorithm from O (n) to O (n 2 ) as each indexOf()
is O (n).
Using Set
instead Array
uses hashing, which changes your lookup times, using has()
for duplicates from O (n) to O (1), which makes the algorithm fall back to a total of O (n).
source to share
Instead of clicking on the singles, simply highlight the frequency array and increase the frequency as you go through the original array. The first time the frequency is 2, you have the earliest duplicate.
Increasing by '1, the frequency in the i-th element of the array will be faster and then click on the array and then anytime on it.
source to share
Try it. This should give you faster speed in cases where there are no duplicates in the 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];
}
}
}
source to share