Problem overview
The method RemoveDuplicates receives an int[] nums and returns a new int[] holding each value once. The result may be in any order, so a solution does not have to keep the original sequence.
For [2, 3, 1, 1, 4, 3, -2, 1] the unique values are 2, 3, 1, 4, -2. The statement shows them in order of first appearance, but any permutation of those five numbers is accepted.
The statement asks for O(n) time and O(n) extra space.
Approach: let a set do the work
A set is a collection that never holds the same value twice. Adding a value that is already present changes nothing. So if you add every element of the array to a set, what remains is exactly the unique values.
A HashSet<int> does each add in constant time on average, so one pass over the array costs O(n). The alternative of checking each element against everything kept so far is O(n²). The lesson's other approaches handle the same task differently, but a hash set is the most direct way to meet the linear time limit.
The last task is the type: the method must return an int[], and the set is not an array. One call converts it.
Step by step
- Create
uniqueValues, an emptyHashSet<int>. It will hold one copy of each value. - Loop over
numsand add each value. Withforeach (int value in nums), calluniqueValues.Add(value). When the value is already there,Addreturnsfalseand leaves the set unchanged, so noContainscheck is needed. - Convert and return.
uniqueValues.ToArray()copies the set's elements into a newint[], and the method returns it.
The solution in C#
class Solution {
public int[] RemoveDuplicates(int[] nums) {
HashSet<int> uniqueValues = new HashSet<int>();
foreach (int value in nums) {
uniqueValues.Add(value);
}
return uniqueValues.ToArray();
}
}
Some C# details:
ToArray()comes from LINQ. It is an extension method inSystem.Linq, so a file of your own needsusing System.Linq;.HashSet<T>itself needsusing System.Collections.Generic;. Both work on any sequence, not only on sets.- Order. A hash set makes no promise about the order of its elements. In practice, a set that only ever had items added tends to list them in insertion order, but your code must not rely on that. This lesson is fine either way, because the result may be in any order.
- A new array. The returned array is a fresh copy. Changing it does not touch
nums, and the input array is never modified. - Sizing. Arrays have a fixed length in C#. That is why the solution collects into a set first: the number of unique values is not known until the loop is done, and
ToArray()then creates an array of exactly that size. - A one-line alternative.
new HashSet<int>(nums).ToArray()ornums.Distinct().ToArray()gives the same values. The loop above shows what those do internally.
Complexity
Time: O(n). The loop makes n calls to Add, each constant time on average, and ToArray() copies at most n values.
Space: O(n). The set and the returned array each hold up to n values when nothing is duplicated.
Edge cases and common mistakes
- Empty input. The set stays empty and
ToArray()returns an empty array, notnull. - No duplicates.
[1, 2, 3]comes back with the same three values. - All equal.
[5, 5, 5]gives[5]. - Expecting sorted output. A hash set does not sort. If the order mattered, you would sort the result explicitly, for example with
Array.Sort. - Returning the set. The method's return type is
int[], so returninguniqueValuesdirectly does not compile. - Missing
usinglines. An error such as "HashSet could not be found" or "does not contain a definition for ToArray" almost always means a missingusingdirective.
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives the five values2, 3, 1, 4, -2in some order.[5, 5, 5]gives[5].[]gives[].