jmichelin/prompt-solution-first-dup-number.md

Created February 2, 2018 21:32

Star (0) You must be signed in to star a gist
Fork (0) You must be signed in to fork a gist

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/jmichelin/8aa795364eeaa71abca449db06d26c4b.js"></script>
Save jmichelin/8aa795364eeaa71abca449db06d26c4b to your computer and use it in GitHub Desktop.

Raw

Prompt

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.

Examples

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment