The question was to 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.
I used the Multiple Pointers Pattern to solve this question so that it has time complexity of O(n) and space complexity of O(1). I used two different approaches, one with a for loop and one with a while loop.
Which of these approaches is better?
function countUniqueValues(arr) {
if (arr.length === 0) return 0;
let pointer1 = 0;
for (let pointer2 = 1; pointer2 < arr.length; pointer2++) {
if (arr[pointer1] !== arr[pointer2]) {
pointer1++;
arr[pointer1] = arr[pointer2];
}
}
return pointer1 + 1;
}
function countUniqueValues(arr) {
if (arr.length === 0) return 0;
let pointer1 = 0;
let pointer2 = pointer1 + 1;
while (pointer2 < arr.length) {
if (arr[pointer1] !== arr[pointer2]) {
pointer1++;
arr[pointer1] = arr[pointer2];
pointer2++;
} else if (arr[pointer1] === arr[pointer2]) {
pointer2++;
}
}
return arr.slice(0, pointer1 + 1).length;
}
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Using for instead of while loop with exactly the same idea is not a different approach.
The logic is correct but it could have been way simpler. You want to find the those positions in arrays where the elements are different (borders). Now your final answer is <#border>+1.
let border = 0;
for (let i = 1; i < arr.length; i++) {
if (arr[i - 1] != arr[i]) {
border++;
}
}
return border+1;
You do not need to change the array, you do not need to keep two pointers.