C# / .NET Junior (0–2 yrs) Coding Frequent C# arrays HashSet O(n)

Find all duplicate integers in an array in O(n) time

cs-jun-002

Your answer

Answer as you would in a real interview — explain your thinking, not just the conclusion.

Model answer

I use a HashSet<int> to track seen values in a single pass. For each element, if it is already in the set it is a duplicate — add it to a result HashSet (to avoid reporting the same duplicate twice). This is O(n) time and O(n) space. A common mistake is using a result List and ending up with the same value reported multiple times; using a result HashSet guarantees uniqueness.

Code example

public static IEnumerable<int> FindDuplicates(int[] nums)
{
    var seen = new HashSet<int>();
    var duplicates = new HashSet<int>();
    foreach (var n in nums)
    {
        if (!seen.Add(n))
            duplicates.Add(n);
    }
    return duplicates;
}

// Test
var result = FindDuplicates(new[] { 1, 2, 3, 2, 4, 3, 5 });
Console.WriteLine(string.Join(", ", result)); // 2, 3

Follow-up

How would you solve this in O(1) extra space if the array values are bounded by the array length?