Speeding up this code for javascript code files firstDuplicate () function
Per Codefighters:
Note. Write a solution with O (n) time complexity and O (1) extra because this is what you are asked to do during a real interview.
Given an array a containing only numbers in the range 1 to a.length, find the first duplicate number for which the second occurrence has the minimum index. In other words, if there is more than 1 duplicate number, return the number for which the second occurrence has a lower index than the second occurrence of the other number. If there are no such elements, return -1. In the meantime, there is no need to worry about it. ”
Example
For a = [2, 3, 3, 1, 5, 2], the output must come first. Duplicate (a) = 3.
There are 2 duplicates: the numbers 2 and 3. The second occurrence of 3 has a lower index than the second occurrence of 2, so the answer is 3.
For a = [2, 4, 3, 5, 1], the output must be first. Duplicate (a) = -1.
So here's what I came up with. It works, but failed the final test as it exceeded 4000ms. I am at a loss as to what else I can do. Any ideas for speeding up?
function firstDuplicate(a) {
var test = [],
lowest = undefined;
for (var i=0; i<a.length; i++) {
if (test.indexOf(a[i]) > -1) {
lowest = lowest || i;
if (i < lowest) {
lowest = i;
}
}
else {
test.push(a[i]);
}
}
return lowest ? a[lowest] : -1;
}
Here was my second try but still failed the last test ...
function firstDuplicate(a) {
var low = undefined,
last = -1;
for (var i=0; i<a.length; i++) {
last = a.lastIndexOf(a[i])
if (last > i && (low === undefined || last < low)) {
low = last;
}
}
return low !== undefined ? a[low] : -1;
}
source to share
Requirements provide a clue to solving this. The set of numbers contained in an array must meet the following criteria:
only numbers in the range 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 this understanding, we are able to keep track of the numbers we have already seen. We can think of numbers as indices in an array, change an element in this index (in this case, making it negative), and if we type one number and the element in this index is less than zero, then we know that we saw 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 Wrong Answer
Keep track of which numbers have already been seen and return the first one that was seen earlier.
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 noted in the comments, this answer takes O (n) extra space, not O (1) extra space.
source to share
We'll take advantage of the fact that the array a
only contains numbers in the range 1 through a.length
to remember that the value was seen by changing the sign of what's at 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]));
You repeat n
once in both examples.
What if the array length was 200,000,000 and the first duplicate was found at index 3? The cycle is still running 200,000,000 times unnecessarily.
So the idea is to break out of the loop as soon as you find the first duplicate. you can use break or just return
.
source to share