# Determine whether an array contains duplicate values

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;

}
return false;
}

• are you sure it's O(n) ? because the Contains has an iterator as well which puts it O(n^2)
– iSR5
Nov 12 '21 at 7:24
• stackoverflow.com/a/20507592/648075 (note that this is for an older version of .NET, more recent versions might have implemented this differently.) Nov 12 '21 at 7:27
• @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.
– iSR5
Nov 12 '21 at 7:33
• I think your counting is incorrect, because set containment is usually O(log n), and I don't see how C# can outperform that. Nov 12 '21 at 7:53
• From a clean code perspective GroupBy is probably the best approach Nov 13 '21 at 12:42

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++)
{

• How about a one liner: return new HashSet<int>(nums).Count < nums.Length ? Nov 12 '21 at 20:46