Start learning free

LESSON 239 OF 674 · SETS

Remove Repeats in C#: Keep the First Copy With a HashSet

Practice Read the full explanation

You get a List of integers nums. Some values may appear more than once.

Return a new List that has each value only once.

Keep the first copy of each value and drop the later ones. The values stay in the order they first appear in nums.

 

Example 1:

Input: nums = [3, 1, 3, 2, 1]
Output: [3, 1, 2]
Explanation: The second 3 and the second 1 are repeats.
They are dropped, and 3, 1 and 2 stay in their order.

Example 2:

Input: nums = [6, 6, 6, 6]
Output: [6]
Explanation: Only the first 6 stays.

Example 3:

Input: nums = [4, 9, 2]
Output: [4, 9, 2]
Explanation: No value repeats, so every number stays.

 

Constraints:

  • nums has at least one number.
  • Every number is between -109 and 109.
STEP 1 OF 7
    Ctrl + Enter to check

    C# · SETS

    Remove Repeats in C#, explained

    Problem overview

    The method RemoveRepeats gets a List<int> named nums. Some values may appear more than once. It returns a new list that has each value only once. The first copy of each value stays, later copies are dropped, and the values keep the order in which they first appear.

    For [3, 1, 3, 2, 1] the answer is [3, 1, 2]: the second 3 and the second 1 are repeats. For [6, 6, 6, 6] it is [6], and for [4, 9, 2] nothing repeats, so the list comes back unchanged.

    Approach

    Read the numbers from left to right. For each one, ask: have I met this value before? If not, it is a first copy, so it goes into the result. If so, skip it.

    The question "have I met it?" is what a HashSet<int> answers quickly. Keep a set named seen next to the result list. The list holds the answer in the right order; the set holds the same values for fast checking. A set alone would lose the order, and a list alone would have to search itself for every number.

    Step by step

    1. Create an empty HashSet<int> named seen.
    2. Create an empty List<int> named result.
    3. Loop over nums with foreach, in order, so first copies are met before later ones.
    4. Test !seen.Contains(num). The ! turns the answer around: the test is true when the value is new.
    5. Add num to result inside the if.
    6. Add num to seen in the same if, so the next copy is recognised.
    7. Return result after the loop.

    The solution in C#

    class Solution {
    public List<int> RemoveRepeats(List<int> nums) {
        HashSet<int> seen = new HashSet<int>();
        List<int> result = new List<int>();
        foreach (int num in nums) {
            if (!seen.Contains(num)) {
                result.Add(num);
                seen.Add(num);
            }
        }
        return result;
    }
}

    The details worth knowing:

    • A List<int> grows with Add; you don't need to know the final size in advance, as you would with an array.
    • The lesson's tests print the list as values separated by spaces. The method returns the list itself, not text.
    • Because Add on a set returns false for a repeat, the test and the insertion could be combined: if (seen.Add(num)) { result.Add(num); }. The version above keeps the two steps apart so each is easy to see.

    Tracing the first example

    numnew value?result after
    3yes[3]
    1yes[3, 1]
    3no[3, 1]
    2yes[3, 1, 2]
    1no[3, 1, 2]

    Testing

    On the statement's three examples, the method returns:

    [3, 1, 2]
[6]
[4, 9, 2]

    Edge cases and common mistakes

    • Building the answer from a set alone. new HashSet<int>(nums) drops the repeats, but a set promises no order, so the first-appearance order isn't guaranteed.
    • Forgetting to add to seen. Then no value is ever recognised as a repeat, and the result equals the input.
    • Returning inside the loop. A return there would end the method after the first value. Return after the loop.
    • Dropping the first copy instead of the later ones. Keeping the last copy gives [3, 2, 1] for the first example, which is a different answer.
    • Negative values. Numbers go down to -1,000,000,000, and a set treats them like any other int. Nothing special is needed.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free