Speeding up this code for codefighters javascript firstDuplicate() function
The requirements give a clue of how to solve this. The set of numbers contained in the array must match the following critera:
only numbers in the range from 1 to a.length
In other words, only positive numbers that are less than or equal to the length of the array. If the array contains ten numbers, none of them will be greater than 10.
With that insight, we have a means of keeping track of numbers that we have already seen. We can treat the numbers themselves as indexes into the array, modify the element at that index (in this case by making it negative) and if we run into the same number and the element at that index is less than zero, then we know we have seen it.
console.clear()
const test1 = [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]
function firstDuplicate(a) {
for (let i of a) {
let posi = Math.abs(i) - 1
if (a[posi] < 0) return posi + 1
a[posi] = a[posi] * -1
}
return -1
}
console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))
console.log(firstDuplicate([2,2]))
console.log(firstDuplicate([2,3,3]))
console.log(firstDuplicate([3,3,3]))Original Incorrect Answer
Keep track of what numbers have already been seen and return the first one that has been seen before.
console.clear()
const test1 = [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]
function firstDuplicate(a){
const seen = {}
for (let v of a){
if (seen[v]) return v
seen[v] = v
}
return -1
}
console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))As pointed out in the comments, however, this answer takes O(n) additional space, not O(1) additional space.
We will take advantage of the fact that the array a contains only numbers in the range from 1 to a.length, to remember that a value has been seen by reversing the sign of whatever is in that position in the array.
function lowestDuplicate(arr) {
for (let i = 0; i < arr.length; i++) {
const val = Math.abs(arr[i]);
if (arr[val - 1] < 0) return val;
arr[val - 1] = -arr[val - 1];
}
return -1;
}
console.log(lowestDuplicate([1, 2, 3, 4, 3, 2, 1]));
console.log(lowestDuplicate([1, 2, 3, 4, 5]));
console.log(lowestDuplicate([5, 4, 3, 2, 2]));
console.log(lowestDuplicate([2, 2]));
console.log(lowestDuplicate([2, 3, 3]));
console.log(lowestDuplicate([3, 3, 3]));
console.log(lowestDuplicate([2, 3, 3, 1, 5, 2]));