Solving CodingSignal's First Duplicate problem

Here is the prompt for the question:

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. If there are no such elements, return -1.

We'll be taking advantage of the object data structure to solve this problem. The property of the object that will be coming in handy is that object's can only store unique keys. This will allow us to only make 1 pass through the array and keep track of what we have already seen.

const a = [2, 1, 3, 5, 3, 2]

function firstDuplicate(a) {
  let obj = {}
  for (let i = 0; i < a.length; i++) {
      if (obj[a[i]]){
          return a[i]
      } else {
          obj[a[i]] = 1;
      }
  }
  return -1
}

firstDuplicate(a) // 3

So taking a look at our code here, we immediately create the object where we will be storing our keys.

To iterate through the array, we'll just be using a for loop. For each item in the array, we will be checking if the value is already a key in our object. If it is not in our object already, we will creating that key. If it is already in our object, we know that we've already seen that number before in our array. At that point, all we have to do is return that number!

It really is that simple to solve this problem. And we've taken advantage of the object to get a linear, O(N), solution.