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.