Unique Value Counter Algorithm using the Multiple Pointer method

Given I have a sorted array of numbers, I want to know how many unique values are within that array.

countUniqueValues(arr)

The array passed into the function will always be a sorted list of numbers. The numbers can be negative, zero, or positive. The algorithm should return the number of unique values in the array. An empty array should be expected to be passed into the algorithm. In the case of an empty array, it should return 0 since there are no values at all.

Examples

countUniqueValues([1,1,1,1,1,2,3,4])                           // Return: 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13])                  // Return: 7
countUniqueValues([])                                          // Return: 0 
countUniqueValues([-5,-4,-2,-1,-1,0,0,1,1,1,1,2,2,3,5,7,7,19]) // Return: 11 

Let's break it down!

There are a few ways we can write this algorithm.
In this article, we will be using the Multiple Pointer method.
The first pointer will start at index 0 and the second at index 1

[1,1,1,1,1,2,3,4]
 ^ ^
 0 1

We will then compare the value at the first pointer to the value at the second pointer.
If they are equal to each other, then the value at the second pointer is not unique and the second pointer moves forward by 1

[1,1,1,1,1,2,3,4]
 ^   ^
 0   2

We can continue this until we hit a unique value

[1,1,1,1,1,2,3,4]
^          ^
0          5

Now that the value at pointer 1 is not equal to the value at pointer 2, we will move the first pointer forward by 1 and set the value at pointer 1's new position to the value to pointer 2

[1,2,1,1,1,2,3,4]
   ^       ^
   1       5

We will repeat this step until a repeat value appears or the array is finished.

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

[1,2,3,4,1,2,3,4]
       ^       ^
       3       7

Now that we have evaluated all the elements in the array, we can see that the first pointer is at index 3.
We can use the first pointers index to determine how many unique values there are in the array by adding 1 to it and returning that value.
index of 3 + 1 = 4 unique values

Pseudo Code

Let's start psuedo coding what we just went over.
The first thing we should do is deal with the empty arrays that are passed through.

+// if arr is empty, return 0

Next, we can declare our first pointers index.

// if arr is empty, return 0
+// define pointer i equal to 0

Then, we will loop over the array and use the variable from the for loop as our second pointer.
If the value at pointer 1 is not equal to the value at pointer 2, we will move the first pointer forward by 1 and set the value at pointer 1's new position to the value to pointer 2

// if arr is empty, return 0
// define pointer i equal to 0
// loop over the arr where j equals 1
+// if the element at i is not equal to the element at j, i++ and set element at i equal to element at j

Finally, once all elements have been evaluated, we can return the first pointers index plus 1 to equal the count of unique values.

// if arr is empty, return 0
// define pointer i equal to 0
// loop over the arr where j equals 1
// if the element at i is not equal to the element at j, i++ and set element at i equal to element at j
return i + 1;

Let's code!

First, let's return 0 if the array is empty

// if arr is empty, return 0
if (arr.length === 0) return 0;

Next, we can declare our first pointers index.

if (arr.length === 0) return 0;
// define pointer i equal to 0
let i = 0;

Then, we will loop over the arr and use the variable from the for loop as our second pointer.
If the value at pointer 1 is not equal to the value at pointer 2, we will move the first pointer forward by 1 and set the value at pointer 1's new position to the value to pointer 2

if (arr.length === 0) return 0;
let i = 0;
// loop over the arr where j equals 1
for (let j = 1; j < arr.length; j++) { // Notice we are setting j = 1 to use it as our second pointer and save memory
    // if the element at i is not equal to the element at j
    if (arr[i] !== arr[j]) {
        // i++ and set element at i equal to element at j
        i++;
        arr[i] = arr[j];
    }
}

Finally, once all elements have been evaluated, we can return the first pointers index plus 1 to equal the count of unique values.

if (arr.length === 0) return 0;
let i = 0;
for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
        i++;
        arr[i] = arr[j];
    }
}
return i + 1;

We now have an algorithm to count the unique values in a sorted list of numbers!
The time complexity of this algorithm is O(N) - Linear Time
The space complexity of this algorithm is O(1) - Constant Time