First Duplicate
Example:
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.
- For a = [2, 1, 3, 5, 3, 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 the second occurrence of 2 does, so the answer is 3.
- For a = [2, 4, 3, 5, 1], the output should be
- firstDuplicate(a) = -1.
Algorithm:
1 Iterate over array elements, if array value - 1 which corresponds to a valid index, contains a negative value, then it has already been encountered, therefore return the array value as the first duplicate value encountered. If not, assign the value corresponding to array value -1 index to be equal negation of the existing value, so that when we encounter its duplicate, the above if condition of array value - 1 will be negative and hence the first duplicate value is duly returned.
2 Another solution would be to keep adding the elements in the array to a hashset and upon encountering an already existing element to be added, instead of adding it we return the duplicate element. While both techniques incur a time complexity of T O(n), there is an extra space complexity of S O(n) in the case of hashset solution.
Test:
1 Test with all unique elements in the array.
2 Test with an array with a singular element
3 Test with multiple duplicate elements in the input array.
Solution:
int firstDuplicate(int[] a) {
for(int i=0;i<a.length;i++)
if(a[Math.abs(a[i])-1]<0)
return Math.abs(a[i]);
else{
a[Math.abs(a[i])-1]=-a[Math.abs(a[i])-1];
}
return -1;
}
// T O(n) S O(1)
int firstDuplicate(int[] a) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < a.length; i++ ) {
if (set.contains(a[i])) {
return a[i];
}
set.add(a[i]);
}
return -1;
}
// T O(n) S O(n)
//https://gist.github.com/harycane/aa034fdb4f7ddeed566554f37d36543d
Complexity Analysis:
Time complexity in both the solutions are T O(n), but in the case of using a hashset there is an extra space complexity of S O(n).