Per Codefighters:
Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.
Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.
Example
For a = [2, 3, 3, 1, 5, 2], the output should be firstDuplicate(a) = 3.
There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.
For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.
So here is what I came up with. It works but fails on the final test because it ran over 4000ms. I'm at a loss as to what else I can do. Any Ideas to improve speed?
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 attempt but still failing on 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;
}4 Answers
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.
11We 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]));Python 3 version that passes the tests.
def firstDuplicate(a): oldies={} notfound=True for i in range(len(a)): try: if oldies[a[i]]==a[i]: notfound=False return a[i] except: oldies[a[i]]=a[i] if notfound: return -1 You are iterating n times in both examples.
What if the array length was 200,000,000 and the first duplicate was found at index 3? The loop is still running 200,000,000 times unnecessarily.
So the idea is to break out of the loop once you find the first duplicate.
you can use break or just return.
