4
\$\begingroup\$

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

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;
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ How about a one liner: return new HashSet<int>(nums).Count < nums.Length ? \$\endgroup\$ Nov 12 '21 at 20:46
  • 1
    \$\begingroup\$ This would add all items first where in my answer it would return at the first duplicate. \$\endgroup\$
    – Heslacher
    Nov 13 '21 at 8:19
  • \$\begingroup\$ ah I like this thank you! \$\endgroup\$
    – d0rf47
    Nov 13 '21 at 15:05
  • \$\begingroup\$ @Heslacher yes. \$\endgroup\$ Nov 13 '21 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.