Finding the first duplicate in an array My code returns the correct answer the first duplicate is 3 (represented as int f) . I am struggling finding a more efficient way to find the first duplicate? 

My constraints are \$ 1 ≤ a.length ≤ 10^5, 1 ≤ a[i] ≤ a.length \$ . 

class Program
{
  static void Main(string[] args)
  {
    int[] a = {2, 3, 3, 1, 5, 2};

    int f = FirstDuplicate(a);

    Console.ReadLine();
   }
public static int FirstDuplicate(int[] a)
{

    int[] answer = new int[2];
    answer[0] = -1;
    answer[1] = a.Length;
    for (int i = 0; i &lt; a.Length - 1; i++)
        for (int j = i; j &lt; a.Length; j++)
            if (a[i] == a[j] &amp;&amp; i != j)
            {
                if (i &lt; answer[1])
                {
                    answer[0] = a[i];
                    answer[1] = j;
                    break;

                }
            }

    return answer[0];
  }
}
For a small array or list of a handful of items, this should be very fast.  But is it efficient as you would scale out?  No.

Before getting on to a better way to achieve the it for a larger number of items, let's look at your current code.  You have some checks that aren't needed.

if (a[i] == a[j] &amp;&amp; i != j)


The check of i != j is not needed if you were to simply initialize j to be i + 1 as in:

for (int j = i + 1; j &lt; a.Length; j++)
    if (a[i] == a[j])


The check of if (i &lt; answer[1]) is totally unnecessary.  In fact, answer as an array is not needed at all as you do not really do anything meaningful with answer[1].

But having 2 loops is not efficient as the input array could be larger.  As mentioned in a comment, the use of a HashSet could be used.  I am changing a few things.  


The method signature is now IEnumerable&lt;int&gt; to allow for arrays,
lists, or any collection of integers.
I use a HashSet to keep track of items I have already
encountered.
The return type is a Nullable&lt;int&gt;, also written as int?, so that
if there are no duplicates found a null is returned.


The resulting method also looks cleaner.  Someone looking at this understands more readily what the code is trying to achieve:

public static int? FirstDuplicate(IEnumerable&lt;int&gt; items)
{

    HashSet&lt;int&gt; set = new HashSet&lt;int&gt;();
    foreach (int item in items)
    {
        if (set.Contains(item))
        {
            return item;
        }
        set.Add(item);
    }
    return null;
} 


As shown in @Denis's answer, and echoed by @Corak, is the method could be made slightly faster and shorter by reducing the logic inside the foreach loop:

if (!set.Add(item))
{
    return item;
}


While this again is slightly faster, slighter cleaner, and recommended in practice, it still lags well behind @vnp 's array solution.

UPDATED Worst Case Array

I composed a worst case array to test of 100000 items where the very last item is the first duplicate of the 2nd to last item.  Your code and mine returned the correct value.  

public static int[] WorstCaseArray
{
    get
    {
        int[] items = new int[(int)Math.Pow(10, 5)];
        for (int i = 0; i &lt; items.Length; i++)
        {
            items[i] = i + 1;
        }
        items[items.Length - 1] = items[items.Length - 2];  
        return items;
    }
}


UPDATE #2 - Worst Case

Obviously we should be working with the largest array allowed.

As @PeterCordes states in a comment to @vnp's answer, the list should be randomized.

As @Denis states, the worst case for a HashSet would be if the only duplicate was the first and last item.  An extremely close second would be if the last and 2nd to last item were the only duplicate.  Note this second worst case for HashSet would be the worst case for @vnp's array solution, so I will use it as my worst case.

public static int[] WorstCaseArray
{
    get
    {
        // Worst case is largest allowed array ...
        int max = (int)Math.Pow(10, 5);
        int[] items = new int[max];
        for (int i = 0; i &lt; items.Length; i++)
        {
            items[i] = i + 1;
        }
        // ... that is randomly shuffled ...
        Shuffle(items);
        // ... with the only duplicate being the last item matching the 2nd to last!
        items[items.Length - 1] = items[items.Length - 2];   
        return items;
    }
}

private static Random random = new Random();
public static void Shuffle(int[] items)
{
    //Fisher-Yates method to shuffle
    for (int i = items.Length - 1; i &gt; 0; --i)
    {
        int randomIndex = random.Next(i + 1);
        int temp = items[i];
        items[i] = items[randomIndex];
        items[randomIndex] = temp;
    }
}


UPDATED Worst Case Timings:


Yours: 14.5105877 seconds
Mine : 00.0065640 seconds
vnp's: 00.0012733 seconds


Tiny array with many duplicates

However, as I said for only a handful of items yours is quite fast.  The problem is - it produces the wrong answer!  Using this array:

int[] array =  new[] { 1, 2, 3, 4, 5, 6, 3, 4, 5, 6 };


Where the expected answer would be 3, yours returns 6.


Yours: took 0.0006141 seconds but returned 6 (wrong)
Mine : took 0.0006162 seconds 
vnp's : 0.0003843 seconds


Large, Random Array with No Duplicates

To round out the answer, let's look at the largest allowed array, randomized, but without any duplicates.  Using the shuffle routine from above:

public static int[] NoDuplicates()
{
    int[] items = Enumerable.Range(1, (int)Math.Pow(10, 5)).ToArray();
    Shuffle(items);
    return items;
}


Timings:


Yours: 15.1978462 seconds
Mine  : 00.0055364 seconds
vnp's : 00.0014876 seconds


BEST ANSWER

Also, since you have tagged this question with [time-limit-exceeded], vnp's answer is not just clever, but also the fastest in all tested scendarios, which makes it the best answer (regarding performance).