Start learning free

LESSON 235 OF 667 · SETS

Remove Repeats in C++: Keep First Copies with a Set

Practice Read the full explanation

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

Return a new vector 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 function removeRepeats gets a vector of integers nums and returns a new vector in which each value appears once. The first copy of each value stays, later copies are dropped, and the values keep the order in which they first appear in nums.

    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. For {4, 9, 2} nothing repeats, so all three numbers stay. The tests print a vector as its values separated by spaces.

    Approach

    Read the numbers from left to right and remember which values you have met. For each number, one of two things is true:

    • it isn't in the memory yet, so this is its first copy: add it to the result and to the memory;
    • it is in the memory, so it is a repeat: skip it.

    A plain unordered_set can't give back the values in the order they first appeared, so it can't be the answer by itself. That is why there are two containers: the vector result keeps the order, and the set seen answers "have I met this value?" quickly.

    Step by step

    1. Create an empty unordered_set<int> named seen.
    2. Create an empty vector<int> named result.
    3. Loop over nums from the first value to the last, with an int named num. Reading in order is what keeps the first copy.
    4. Test for a first copy: seen.count(num) == 0 means num isn't in the set.
    5. Add it to the end of result with push_back.
    6. Add it to seen with insert, so that a later copy is skipped.
    7. Return result after the loop.

    The solution in C++

    class Solution {
public:
    vector<int> removeRepeats(vector<int>& nums) {
        unordered_set<int> seen;
        vector<int> result;
        for (int num : nums) {
            if (seen.count(num) == 0) {
                result.push_back(num);
                seen.insert(num);
            }
        }
        return result;
    }
};

    Notes on the C++:

    • The vector is taken by reference, so it isn't copied. The function builds and returns a new vector and leaves nums as it was.
    • count on a set is 0 or 1, so comparing it with 0 is a membership test. C++17 has no contains.
    • Returning result by value is cheap: the compiler moves it out.

    Complexity

    Time is O(n) on average: each number costs one set lookup and, for a first copy, one insert and one push_back, each constant on average. Space is O(n) for the set and the result in the worst case, when every value is different.

    Edge cases and common mistakes

    • Building a set from the whole vector. unordered_set<int>(nums.begin(), nums.end()) drops the repeats, but the set has no order, so the first-appearance order is lost.
    • Forgetting to insert into seen. Then every number looks new and the result is a copy of nums.
    • Returning inside the loop. The function would return after the first value.
    • Negative numbers and large values. They work the same way; values up to a billion in size fit in an int.

    Testing

    • {3, 1, 3, 2, 1} gives 3 1 2.
    • {6, 6, 6, 6} gives 6.
    • {4, 9, 2} gives 4 9 2.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free