# First Duplicate Algorithm

# First Duplicate

Solution to the “First Duplicate” problem in C#.

## Problem

Given an array that contains only numbers in the range 1 to array.Length, find the first duplicate number for which the second occurrence has the minimal index. If there is no such number, return -1.

**Note:** Write a solution with O(n) time complexity and O(1) additional space complexity.

Check the complete project on my Github

### Example

Input:

```
[2, 3, 3, 1, 5, 2]
```

Output:

```
3
```

There are 2 duplicates: 2 and 3. the second occurrence of 3 has smaller index (position 2 of the array) than the second occurrence of 2 (position 5 of the array). Hence the first duplicate is 3.

Input:

```
[2, 4, 3, 5, 1]
```

Output:

```
- 1
```

There is not duplicated numbers in the array.

## Solution

```
using System;
using System.Collections.Generic;
namespace FirstDuplicate
{
class Program
{
public static int FirstDuplicate(int[] a)
{
HashSet<int> set = new HashSet<int>();
for(var i = 0; i <= a.Length - 1; i++)
{
if (set.Contains(a[i]))
{
return a[i];
}
set.Add(a[i]);
}
return -1;
}
static void Main(string[] args)
{
int[] arr = {2, 3, 3, 1, 5, 2};
Console.Write(FirstDuplicate(arr));
Console.ReadLine();
}
}
}
```

### Constraints

```
1 <= array.Length <= 10^5
1 <= array[i] <= a.length
```