Skip to content

Instantly share code, notes, and snippets.

@torressam333
Created December 13, 2022 01:02
Show Gist options
  • Save torressam333/fc1f6417ec649ceacfd8a736e56edd7b to your computer and use it in GitHub Desktop.
Save torressam333/fc1f6417ec649ceacfd8a736e56edd7b to your computer and use it in GitHub Desktop.
Gist demonstrating 3 different O(n) Methods For Getting Unique Values Count in JavaScript
/**
* Count Unique Values Problem solved 3 ways
*
* Prompt: Implement a function which accepts a sorted array and counts
* the unique values in the array.
*
* Negative numbers are allowed and will only be numbers.
* The array is always sorted*
*
* @param {*} sortedArr
* @returns
*/
// Using a set O(n) time complexity
const countUniqueValuesWithSet = (sortedArr) => {
if (!sortedArr.length) return [];
const charSet = new Set(sortedArr);
const uniqueArray = Array.from(charSet);
return uniqueArray.length;
};
// Using sliding pointer + same array -> O(n) t.c.
const countUniqueValues = (sortedArr) => {
if (!sortedArr.length) return [];
let i = 0;
for (let j = 0; j < sortedArr.length; j++) {
if (sortedArr[i] !== sortedArr[j]) {
i++;
sortedArr[i] = sortedArr[j];
}
}
return i + 1;
};
// Using the sliding pointer approach and new array -> O(n) t.c.
const countUniqueValues2 = (sortedArr) => {
if (!sortedArr.length) return [];
const store = [];
for (let i = 0; i < sortedArr.length; i++) {
let j = i + 1;
sortedArr[i] === sortedArr[j] ? j++ : store.push(sortedArr[j]);
}
return store.length;
};
console.log(countUniqueValues([1, 1, 1, 1, 1, 2]));
console.log(countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]));
console.log(countUniqueValues([]));
console.log(countUniqueValues([-2, -1, -1, 0, 1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment