Find First Duplicate is one of a classic interview question that has been asked by google which you can solve in codesignal. But if you are looking for a different solution than yours, here's how I solved it.

Problem

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, 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, 2], the output should be firstDuplicate(a) = 2;
  • For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

Solution

  • Create a hash map to store previously visited numbers
  • If the current number already exists on the map then this would the first duplicate number we are looking for

Complexity: O(N)