First Duplicate Value

Medium — AlgoExpert

Problem:

Given an array of integers, write a function that returns the first integer that appears more than once when the array is read from left to right.

• The important thing to know by reading the problem is that they want the first so we will definitely not be changing the order of the array.

Examples:

array = [2, 1, 5, 2, 3, 3, 4]

result = 2

array = [2, 1, 5, 3, 3, 2, 4]

result = 3

Solution:

Brute Force Pseudocode: With the array, we can iterate through each number and then have a nested loop going through to check the other numbers to see if they match finding a duplicate but you would need to go through the whole array to find the smallest index (meaning the first) duplicate. So you would have a nested loop and a variable holding the smallest index of the duplicate found. If the next duplicate that is found has a smaller index then we would go ahead and replace it with the new value.
- This solution being the brute force would have a time complexity of O(n²)

The following will be a better solution bringing the time complexity to O(n) since we are only traversing through the array once.

function firstDuplicateValue(array) {
  
let map = new Map()	
for(let i = 0; i < array.length; i++) {
	if(map.has(array[i])) {
		return array[i]
	} else {
		map.set(array[i])
	}
   }
  return -1;
}

As you can see above we have set a Hash Map named map.

While going through the loop we check if the map has the array[i] if it does not then we will want to add it to the map but if it does then it means we have found a duplicate so we can automatically return the array[i] since it will be considered the first one. Now outside of the loop if nothing is found then we will make sure to return -1.

I honestly love Hash Maps! They really are a powerful tool. Hope this quick walkthrough helps!