Contains duplicate

Does any value appear twice in the array? A hash set answers in a single pass, no sorting required.

Time O(n)Space O(n)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

HashSet<T>.Add both inserts a value and tells you whether it was already there, in one call. Walk the array once: the first time Add would return false, that value has been seen before, so the array contains a duplicate.

Code

public static bool ContainsDuplicate(int[] a) {
    var seen = new HashSet<int>();
    foreach (int x in a) {
        if (!seen.Add(x)) return true;
    }
    return false;
}

Tips

Add returns a bool - true for a brand new value, false if it was already in the set - so a separate Contains check is never needed.
Sorting first also finds duplicates, in O(n log n). The hash set does it in one O(n) pass.

In the .NET library

A HashSet<T> is really a Dictionary<T,bool> under the hood: the same O(1) average lookup, but it only needs to remember whether a key exists, not a paired value.