Algorithms: Multiple pointers

Multiple pointers

• Creating pointers or values that correspond to an index or position and move towrads the beginning, end or middle based on a certain condition.
• Very efficient for solving problems with minimal space complexity.

Problem 1:

Write a function called sumZero which accpets 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.

function sumZero(arr) {
	let left = 0;
  	let right = arr.length - 1;
  	while (left < right) {
    	let sum = arr[left] + arr[right];
      	if (sum === 0){
        	return [arr[left], arr[right]];
        } else if(sum > 0) {
        	right--;
        } else {
        	left++;
        }
    }
}
sumZero([-3,-2,-1,0,1,2,3]) // [-3,3]
sumZero([-2,0,1,3]) // undefined

Problem 2:

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.

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]
        }
    }
    return i + 1;
}
countUniqueValues([1,2,2,5,7,7,99]) //5
// Move i forward as the i,j index values doesnt match
// then replace the i index value with j index value and continue
//          i   <-- i is the index of the last modified value
// [1,2,5,7,99,7,99]
//               j
// We add +1 to i to get the total count or the length of the answer

countUniqueValues([1,1,1,1,1,2]) //2
countUniqueValues([]) //0
countUniqueValues([-2,-1,-1,-,1]) //4

Problem 3:

Implement a function called, areThereDuplicates which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in.

function areThereDuplicates(...args) {
  // Two pointers
  args.sort((a,b) => a > b);
  let start = 0;
  let next = 1;
  while(next < args.length){
    if(args[start] === args[next]){
        return true
    }
    start++
    next++
  }
  return false
}

//One liner solution
function areThereDuplicates() {
  return new Set(arguments).size !== arguments.length;
}

Problem 4:

Write a function called averagePair. Given a sorted array of integers and a target average, determine if there is a pair of values in the array where the average of the pair equals the target average. There may be more than one pair that matches the average target.

function averagePair(arr, num){
  let start = 0
  let end = arr.length-1;
  while(start < end){
    let avg = (arr[start]+arr[end]) / 2 
    if(avg === num) return true;
    else if(avg < num) start++
    else end--
  }
  return false;
}

averagePair([1,2,3],2.5) // true
averagePair([1,3,3,5,6,7,10,12,19],8) //true
averagePair([-1,0,3,4,5,6],4.1) //false

Problem 5:

Write a function called isSubsequence which takes in two strings and checks whether the characters in the first string form a subsquence of the characters in the second string. In other words, the function should check whether the characters in the first string appear somewhere in the second string, without their order changing.

function isSubsequence(str1, str2) {
  var i = 0;
  var j = 0;
  if (!str1) return true;
  while (j < str2.length) {
    if (str2[j] === str1[i]) i++;
    if (i === str1.length) return true;
    j++;
  }
  return false;
}
isSubsequence('hello', 'hello world') //true
isSubsequence('sing', 'string'); //true
isSubsequence('abc', 'acb') //false (order matters)

//Recursive
function isSubsequence(str1, str2) {
  if(str1.length === 0) return true
  if(str2.length === 0) return false
  if(str2[0] === str1[0]) return isSubsequence(str1.slice(1), str2.slice(1))  
  return isSubsequence(str1, str2.slice(1))
}