DEV Community

Denise Pen
Denise Pen

Posted on

Tackling Algorithms: Counting Unique Values

Problem: Given an array of integers, count the number of unique values.

For example, if we have the following array:

[1, 1, 1, 1, 1, 1, 3, 5]

the count of original values is 3 => 1, 3, and 5.

First Solution: Frequency Counter

The first time I attempted this problem I decided to:
1. Create an empty object, and for every integer encountered either
2. Add that integer to the object or, if that integer is already in the object
3. Increment its value by 1.

Here is my code (using javascript):

function countUniqueValues(arr){

  let newObj = {};                  //created new empty object to hold integer values.

  for (let i=0; i<arr.length; i++){ //iterate over the array


      let char = arr[i];

      if ( newObj[char] > 0 ) {     //if the item is already in newObj 
          newObj[char]++            //increment its value by 1
      } else {
          newObj[char] = 1          //if the integer is not already in newObj put it there with a value of 1
      }

  }
  return Object.keys(newObj).length;   //return length of array returned by Object.keys(newObj)
}
Enter fullscreen mode Exit fullscreen mode

Running countUniqueValues([3,3,3,4,4,4,5,5,5,5,5,6]) returns 4. because there are 4 unique values => 3, 4, 5, and 6.

If we want to see the value of newObj at the end of the function we can put *console.log(newObj) before the final return:

...
}
  console.log(newObj)
  return Object.keys(newObj).length;
}
Enter fullscreen mode Exit fullscreen mode

Running countUniqueValues([3,3,3,4,4,4,5,5,5,5,5,6]) prints a newObj value of


newObj = {
     3: 3, 
     4: 3, 
     5: 5,
     6: 1
}
Enter fullscreen mode Exit fullscreen mode

As you can see there are 4 keys in the object: 3, 4, 5, and 6.

At this point all that is left to do is count the number of keys which we accomplish with Object.keys(newObj).length.

Second Solution: Multiple Pointers

(Taken from this course)

To use this method you must start with a sorted array.

  1. Compare the value at the index of i with the value at the index of j.

  2. If they are equal move j ahead until we find something that is not equal to i.

  3. If they are not equal move i up 1 space and put the value of j into i's new place.

  4. Continue to do this until you have gone through the array completely. 'i' will be at the index of the final unique value. If we add 1 to this index number we will have the total number of unique values.

We will use the same array as above: [3,3,3,4,4,4,5,5,5,5,5,6]

Let's walk through the code:

function countUniqueValues(arr) {
    var i=0;

    for (var j=1; j < arr.length; j++) {
        if(arr[i] !== arr[j]){
            i++;
            arr[i] = arr[j]
        }
    console.log(i,j)
    }
    return i + 1;
}
Enter fullscreen mode Exit fullscreen mode

img

img

After we have gone completely through the array one time every unique value is at the beginning of the array and 'i' is in the position of the final unique value:

img

We see that i is at index 3 so we just add 1 to this to get 4 which is the total number of unique values:

return i + 1
Enter fullscreen mode Exit fullscreen mode

Because we are adding 1 to i this become a problem when we are given an empty array, []. If we were to use the above solution we would get a return value of 1. To combat this we can add a check to the beginning of the function to check for empty arrays:

if (arr.length === 0 ) return 0;

Enter fullscreen mode Exit fullscreen mode

The final function is:

function countUniqueValues(arr) {
  if (arr.length === 0 ) return 0;
    var i=0;

    for (var j=1; j < arr.length; j++) {
        if(arr[i] !== arr[j]){
            i++;
            arr[i] = arr[j]
        }
    console.log(i,j)
    }
    return i + 1;
}
Enter fullscreen mode Exit fullscreen mode

As you can see, the second solution to this problem only runs through the array once and there was no need to create an additional object or count the number of keys of that object so this second solution is much more efficient than the first. Although both solutions should have time complexity of O(n), the second solution is an improvement when it comes to space complexity.

How would you approach this problem?

Top comments (7)

Collapse
 
gmartigny profile image
Guillaume Martigny

One clever solution is to use Set as they have unique values by design:

function countUniqueValues(arr) {
  return new Set(arr).size;
}
countUniqueValues([]); // => 0
countUniqueValues([1, 1, 1, 2, 3, 3]); // => 3

It's not really an algorithm, tho ;)

Collapse
 
anndd profile image
Anna Su** • Edited

... and a lazy solution would be to use underscorejs:

_.uniq([1, 1, 1, 2, 3, 3]).length; //=> 3
Collapse
 
denisepen profile image
Denise Pen

Right... I always forget about sets!

That makes everything so much easier.

Collapse
 
jlarrieux profile image
Jean-Rodney Larrieux

My code wouldn't have been that concise but exact solution I thought of

Collapse
 
adtm profile image
Tomas Eglinskas

I think also you could use this technique I wrote in this post: dev.to/adtm/whats-your-favorite-al... :)

negating numbers on the fly and checking if they exist, if it doesn't - add +1 to the counter.

Collapse
 
darkain profile image
Vincent Milum Jr

What happens when the array isn't pre-sorted?

Collapse
 
denisepen profile image
Denise Pen

If it's not pre-sorted you have to use a different approach - the multiple pointers approach won't work.