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\$ Commented Nov 12, 2021 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\$ Commented Nov 12, 2021 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\$ Commented Nov 12, 2021 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\$ Commented Nov 12, 2021 at 7:53
  • \$\begingroup\$ From a clean code perspective GroupBy is probably the best approach \$\endgroup\$ Commented Nov 13, 2021 at 12:42

1 Answer 1

Reset to default
4
\$\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\$
3
  • 1
    \$\begingroup\$ How about a one liner: return new HashSet<int>(nums).Count < nums.Length ? \$\endgroup\$ Commented Nov 12, 2021 at 20:46
  • 1
    \$\begingroup\$ This would add all items first where in my answer it would return at the first duplicate. \$\endgroup\$ Commented Nov 13, 2021 at 8:19
  • \$\begingroup\$ @Heslacher yes. \$\endgroup\$ Commented Nov 13, 2021 at 20:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.