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
- Build the set from the vector.
unordered_set<int> unique(nums.begin(), nums.end());creates a set and fills it with every element fromnums.begin()up tonums.end(), the start and the end of the vector. - 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 andend()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 returnsint, so the value is converted. The count is at most the number of elements, which fits easily.- Sets are unordered. An
unordered_setkeeps 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 calledstd::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.
