Remove duplicates from an array, preserving first-seen order, in O(n)
Implement RemoveDuplicates(nums) returning a new array with duplicates removed, PRESERVING first-seen order. Requirements: O(n) time using a HashSet<int> — one pass. [3, 1, 3, 2, 1] must return [3, 1, 2] (first occurrences, original order). Do not sort, which would destroy the order.
public static int[] RemoveDuplicates(int[] nums)
{
// your code here
return null;
}Write the implementation.
Walk nums once with a HashSet<int> seen and a List<int> result. For each value, seen.Add(n) returns false if already present — skip it; on true, append to result. Return result.ToArray(). The set gives O(1) membership, so the whole pass is O(n) and order is preserved.
- ✗Sorting first, which destroys the required first-seen order
- ✗Using a nested-loop membership check, making it O(n²) instead of O(n)
- ✗Returning
set.ToArray()directly, which gives no guaranteed insertion order
- →Why does
HashSet.Addreturning a bool save you a separateContainscall? - →How would you dedupe a stream too large to fit in memory?
Task
Return the array's elements with duplicates removed, preserving first-seen order.
public static int[] RemoveDuplicates(int[] nums)
{
var seen = new HashSet<int>();
var result = new List<int>();
foreach (int n in nums)
if (seen.Add(n)) // true only on n's first appearance
result.Add(n);
return result.ToArray();
}How it works
We walk the array once. A HashSet<int> remembers values already seen and gives O(1) membership checks.
The key detail is that seen.Add(n) returns a bool: true when n is added for the first time, false if it was already present. This folds the check and the insert into one action — no separate Contains is needed. On the first appearance the value is appended to result; on a repeat it is skipped.
Because elements are appended to result strictly in the order of their first appearance, the original order is preserved. A single pass with O(1) work per step gives O(n) time. Sorting would break the order, and a nested membership check would make it O(n²).
