Start learning free

LESSON 230 OF 667 · SETS

Unique Count in C++: Counting Distinct Values with unordered_set

Practice Read the full explanation

Given a vector of integers nums, return how many different values it has.

A value that appears several times counts only once.

 

Example 1:

Input: nums = [4, 7, 4, 1, 7]
Output: 3
Explanation: The different values are 4, 7 and 1. The second 4 and the second 7 are repeats, so they don't count again.

Example 2:

Input: nums = [5, 5, 5]
Output: 1
Explanation: Every number is 5, so there is only one different value.

Example 3:

Input: nums = [-2, 0, 3, 8]
Output: 4
Explanation: No value repeats, so every number counts.

 

Constraints:

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

    C++ · SETS

    Unique Count in C++, explained

    Problem overview

    The function uniqueCount receives a vector<int> named nums and returns how many different values it holds. A value that appears several times counts once. The vector has at least one number, and every number is between -1,000,000,000 and 1,000,000,000.

    For [4, 7, 4, 1, 7] the answer is 3, because the different values are 4, 7 and 1. For [5, 5, 5] it is 1, and for [-2, 0, 3, 8] it is 4, since nothing repeats.

    Approach: let a set remove the repeats

    A set holds each value at most once. Adding a value that is already inside changes nothing, and checking whether a value is in the set is fast. If you put all the numbers into a set, the repeats collapse, and the size of the set is the number of different values. In C++ the hash-based set is unordered_set.

    Without a set, you would compare every number with all the others, or sort a copy of the vector and count where neighbouring values differ. The set needs neither: building it is a single pass, and the set does the "have I seen this value?" bookkeeping for you. Take [4, 7, 4, 1, 7]: the set ends up holding 4, 7 and 1, so its size is 3.

    Step by step

    1. Build the set from the vector. unordered_set<int> unique(nums.begin(), nums.end()); creates a set and fills it with every element from nums.begin() up to nums.end(), the start and the end of the vector.
    2. Return its size. unique.size() is the number of values the set holds, and every one of them is different.

    The solution in C++

    class Solution {
    public:
        int uniqueCount(vector<int>& nums) {
            unordered_set<int> unique(nums.begin(), nums.end());
            return unique.size();
        }
    };
    

    The C++ details worth knowing:

    • Iterator pair. begin() points at the first element and end() points one past the last. A container can be built from any such range, which is why the set constructor takes two of them. Elements that are already in the set are skipped while it fills.
    • size() returns an unsigned type. The function returns int, so the value is converted. The count is at most the number of elements, which fits easily.
    • Sets are unordered. An unordered_set keeps no particular order, which doesn't matter here because only the count is needed.
    • The name unique. It is a variable name here. The C++ standard library also has a function called std::unique, but a local variable with that name is allowed.

    A longer way to write it

    The constructor call is a shortcut for two steps: create an empty set, then insert each number in a loop. Writing it that way gives the same answer, which can help while you are learning how sets behave. The shortcut says the same thing in one line.

    Complexity

    Time: O(n) on average for n numbers, since each insertion takes constant time on average. Space: O(k), where k is the number of different values, at most n.

    Edge cases and common mistakes

    • All values equal. [5, 5, 5] gives 1.
    • No repeats. [-2, 0, 3, 8] gives 4, the length of the vector.
    • Returning nums.size(). That counts every element, repeats included.
    • Negative numbers. They are ordinary values for the set.

    Testing

    • [4, 7, 4, 1, 7] gives 3.
    • [5, 5, 5] gives 1.
    • [-2, 0, 3, 8] gives 4.
    Keep going with C++650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free