Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number. (See examples below to see what we mean here by the "first" duplicate).
If there are no such elements, return -1.
Note: Your solution should be O(n) runtime and O(1) space.
Example #1
For [2, 3, 3, 1, 5, 2], the output should be 3.
There are 2 duplicates: numbers 2 and 3.
The 2nd occurrence of 3 has a smaller index than the 2nd occurrence of 2, so the answer is 3.
Example #2
For [2, 4, 3, 5, 1], the output should be -1.