Scribble 11: First Duplicate

Here’s the problem statement:

Given an array of n integers such that every integer lies only in [1, n], find the element in the array who’s duplicate has the minimum index of all the indices that are occupied by duplicate values.

For example:
Array: [3 2 5 2 3]
Output: 2

Approach 1:

This is a naive approach:

Maintain a variable minDuplicateValueIndex to store the smallest index in the array at which a duplicate value exists i.e. to store the index of the first duplicate value in the array. Initialise it to -1.
Loop through the array using an i for loop.
For every element, look ahead in the array to find its duplicate (if any). When a duplicate is found, update minDuplicateValueIndex if needed.
Return array[minDuplicateValueIndex]

Note that we look only ahead and not behind in the array because if there were any duplicates of array[i] before i (say at index j) then earlier in the algorithm only when i was at j, the current i would already have been discovered as a duplicate.

Also note that this approach will work for any values of the elements in the array and does not take any advantage of the fact that the integers in the array lie only in [1, n].

Time complexity: O(N²) because we need a doubly nested loop.

Space complexity: O(1) because we do not use any extra space.

Approach 2:

Loop through the array elements from the left to the right while maintaining a HashSet to store the seen values. If, for any index i, array[i] is already present in the set then we’ve found the first duplicate value (it’s the first one of course because we’re going from the left to the right) and therefore we must simply return array[i].

If we’ve traversed the entire array (and not returned in the middle of the reversal anywhere) then it means that there are no duplicates in the array and so we must return -1.

Note that this approach too, like the first one will work for any values of the elements in the array and does not take any advantage of the fact that the integers in the array lie only in [1, n].

Time complexity: O(N) because every element in the array is visited exactly once.

Space complexity: O(N) to store the seen set

Approach 3:

Let’s try to utilise the fact that the array values lie in [1, n]:

It is interesting to observe that: Since array values lie in [1, n] therefore for every value array[i] in the array, it is possible to access the array[i]th element in the array i.e. the (array[i]-1)th index.

For example: in the array [3 2 5 2 3 ], it is possible to access each of the 3rd, 2nd, 5th, 2nd, 3rd elements respectively i.e. the 2nd, 1st, 4th, 1st, 2nd indices respectively.

Also, it is good to realise that since n is the length of the array and therefore can never be -ve therefore all elements in the array lie in [1, n] so all array elements are +ve values.

Here’s the logic:

While looping through the array from the left to the right using an i for loop, mark array[i] visited by setting the array[i]th element in the array i.e. the value at the (array[i]-1)th index to its -ve. And, whenever you find a value array[i] for which the element at (array[i]-1)th index is -ve it means that the element array[i] has been visited earlier and is therefore a duplicate and it is the first duplicate (because we’re looping from the left to the right) and therefore we must return array[i].

If we’ve traversed the entire array (and not returned in the middle of the reversal anywhere) then it means that there are no duplicates in the array and so we must return -1.

Note that this approach will work only in case the array values lie in [1, n] where n is the length of the array.

Time complexity: O(N) because any element in the array is visited at max twice(once while looking at array[i] and perhaps once while looking at array[array[j]-1]) in the algorithm.

Space complexity: O(1) since no extra space is used.

Here’s the code for this solution in Java:

public int dups(int[] array) {
	for(int n: array) {
		if(array[Math.abs(n)-1]<0) {//if the element is already visited
			return Math.abs(n);
		//need to use Math.abs to check the original array value and not the changed (set to -ve) value 
                }
		else {
			array[Math.abs(n)-1] *=-1;//this marks the element visited
		}	
        }
    	return -1;
  }

Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂

Share this:

Related