Multiple Pointers - rohit120582sharma/Documentation GitHub Wiki
Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on a certain condition.
Very efficient for solving problems with minimal space complexity as well.
Write a function called sumZero which accepts a sorted array of integers.
The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist.
Time Complexity - O(N) and Space Complexity - O(1)
function sumZero(arr){
// Create multiple pointers
var left = 0;
var right = arr.length - 1;
// Run a loop if left < right
while(left < right){
// Check sum
var sum = arr[left] + arr[right];
// If sum is '0', then return an array
if(sum === 0){
return [arr[left], arr[right]];
}
// If sum is bigger than 0, then take right down
else if(sum > 0){
right--;
}
// If sum is lesser than 0, then take left up
else if(sum < 0){
left++;
}
}
}
sumZero([-4, -3, -2, -1, 0, 1, 2, 5, 10]);
sumZero([1, 2, 3]);
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.
Time Complexity - O(N) and Space Complexity - O(1)
function countUniqueValues(arr){
// Check if array is empty
if(arr.length === 0){
return 0;
}
// create pointer
var i = 0;
var n = i + 1;
// Run a loop over array
for(var j=n; j<arr.length; j++){
if(arr[i] !== arr[j]){
i++;
arr[i] = arr[j];
}
}
// return unique count
return i + 1;
}
countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4