Determine whether an array contains duplicate values

Question

My solution for the leet code problem to search an array of ints for duplicate values and return a boolean seems quite efficient (< 90% of submissions runtime). However, I am currently reviewing Data Structures and Algorithms and I wonder if there is a more efficient approach to this, since if my counting is correct my solution will run at O(n) for worst case scenarios. I am still new to C# (I mostly code in js).

public bool ContainsDuplicate(int[] nums) {
 HashSet<int> singles = new HashSet<int>();
 for(int i = 0; i < nums.Length;i++)
 {
 if (singles.Contains(nums[i]))
 return true;
 singles.Add(nums[i]);
 
 }
 return false;
 }

• iSR5: are you sure it's O(n) ? because the Contains has an iterator as well which puts it O(n^2)
• BCdotWEB: stackoverflow.com/a/20507592/648075 (note that this is for an older version of .NET, more recent versions might have implemented this differently.)
• iSR5: @BCdotWEB I just checked it here referencesource.microsoft.com/#System.Core/System/Collections/… (it's still valid on 4.8 .NET) have not validate it on .NET Core yet.
• Toby Speight: I think your counting is incorrect, because set containment is usually O(log n), and I don't see how C# can outperform that.
• Anders: From a clean code perspective GroupBy is probably the best approach

Answer 1

This can be slightly optimized by not using Contains() but checking the returned value from Add(). If the item is allready contained in the HashSet<T> calling Add() will return false.

public bool ContainsDuplicate(int[] nums) {
 HashSet<int> singles = new HashSet<int>();
 for(int i = 0; i < nums.Length;i++)
 {
 if (!singles.Add(nums[i]))
 {
 return true;
 }
 }
 return false;
}

• Jesse C. Slicer: How about a one liner: return new HashSet<int>(nums).Count < nums.Length ?
• Heslacher: This would add all items first where in my answer it would return at the first duplicate.
• Jesse C. Slicer: @Heslacher yes.