Haemin Park | DS & A

Question & Examples

Implement a function called countUniqueValues which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.

// Examples
countUniqueValues([1, 1, 1, 1, 1, 2]) // 2 (unique values)
countUniqueValues([1, 2, 3, 4, 4, 5]) // 5
countUniqueValues([]) // 0

My Solution

// using pointers
function countUniqueValues(arr) {
  if(arr.length === 0) {
    return 0
  }
  let pointer1
  let pointer2
  let total = 0
  // we're looping over arr.length - 1 because
  // the second pointer cannot exceed the length of the array
  for (let i = 0; i < arr.length - 1; i++) {
    pointer1 = i
    pointer2 = i + 1
    if(arr[pointer1] !== arr[pointer2]) {
      total++
    }
  }
  return total
}

This simple function works as long as the array is sorted (which it is according to the question). However, it produces errors when the array is unsorted like this:

countUniqueValues([-100, 2, -4, 1, 1, 4, 5, 76, 2, 3, 2])
 
// 9

Because the function checks for each pairs that has values adjacent to one another, it cannot know the fact that 2 is a unique number. If we console.log() the values both pointers are pointing to, it will be like this:

function countUniqueValues(arr) {
  ...
  for (let i = 0; i < arr.length -1; i++) {
    pointer1 = i
    pointer2 = i + 1
    console.log(arr[pointer1], arr[pointer2])
  }
  ...
}
 
countUniqueValues([-100, 2, -4, 1, 1, 4, 5, 76, 2, 3, 2])
 
// -100 2 V
// 2 -4 V
// -4 1 V
// 1 1
// 1 4 V
// 4 5 V
// 5 76 V
// 76 2 V
// 2 3 V
// 3 2 V

The ones I marked with a V is where the total variable increments by one. As we can see here, even though 2 is a unique value, the total variable increments.

Another way I came up to solve this problem is by counting the frequency of the values in the array. This method seems better as it can be applied to an unsorted array.

// counting the frequencies instead
function countUniqueValues(arr) {
  if(arr.length === 0) {
    return 0
  }
  const frequencyCounter = {}
  for(let val of arr) {
    frequencyCounter[val] = (frequencyCounter[val] | 0) + 1
  }
  return Object.keys(frequencyCounter).length
}

The code above will give us the correct answer.

countUniqueValues([-100, 2, -4, 1, 1, 4, 5, 76, 2, 3, 2])
 
// 8

I actually like this method more than the first one. Anyway, both solutions have the time complexity of O(n).

Counting the number of unique values in a sorted array

Question & Examples

My Solution