Count unique values algorithm in JavaScript
Given a sorted array of values like [1, 1, 2, 3, 3, 4, 5, 5, 5], count the
number of unique values in $O(n)$ time and $O(1)$ space.
If there wasn’t a requirement to do this in $O(1)$ space, the most
straightforward way to do it would be to use a Set(). We could iterate the
input array adding each element to the set, then return set.size. This would
be $O(n)$ time but $O(n)$ space, so it wouldn’t meet the space requirement.
When you see a constant space requirement like this, it’s often a hint that you should re-use the input as working memory in your algorithm to avoid having to use extra space.
In this case, we can use a “caterpillar”, also known as a “multiple pointers” pattern. We rely on the fact that the input values are sorted.
We use two pointers called tail and head (t and h). Tail starts at index
0 and head starts at index 1. We then iterate head through to the end of the
array.
When we find that the values at tail and head are different, we’ve hit a new unique value. We increment tail by one, and also set the value at that new position to the head value, in order to keep comparing to it. Remember that the input values were sorted, so we know we’re not going to see a previously seen value out of sequence. It’s safe to only track the most recently seen value.
You could also think of this as gathering a set of unique values at the
beginning of the input array. For example, given an input of
[1, 1, 2, 3, 3, 4, 5, 5, 5], we’ll end up with [1, 2, 3, 4, 5, 4, 5, 5, 5],
and t will be at index 4, which has value 5.
At the end, we just return t + 1 as that’s the size of the set of unique
values that we have built at the beginning of the input array.
This algorithm is $O(n)$ time and $O(1)$ space.
function countUniqueValues(values) {
var t = 0;
for (let h = 1; h < values.length; h++) {
if (values[t] !== values[h]) {
tail++;
values[t] = values[h];
}
}
return t + 1;
}