JS - Educative-Twopointers-01

Two Pointers

  • The two pointers pattern uses two pointers to iterate over an array or list until the conditions of the problem are satisfied
  • It allows us to keep track of the values of two different indexes in a single iteration.

Pattern that require Two Pointers

  • There is a need to find two data elements in an array that satisfy a certain condition.
  • To avoid using nested loop that has time complexity of O(n**2)
  • Usually involve comparing or swapping values pointed to by two indexes.

Common Problems with this approach

  • Reversing an array
  • Pair Given Sum in a Sorted Array

QUESTION: Valid Palindrome

  • Write a function that takes a string s as input and checks whether it is a palindrome or not.
  • A phrase, word or sequence is a palindrome that reads the same backwards as forwards.

SOLUTION:

Using 2-Pointers
const isPalindrome = (s) => {
  // make sure all lowercase and remove non-alphanumeric characters
  s = s.toLowerCase().replace(/[^a-z]/g, '');
 
  // initialize two pointers, one at beginning and one at the end
  let i = 0,
    j = s.length - 1;
 
  // Move pointers towards each other until they meet in the middle
  while (i < j) {
    // return false is char dont match ==> not a palindrome
    if (s[i] !== s[j]) {
      return false;
    }
    i++; // Move left pointer to the right
    j--; // Move right pointer to the left
  }
  // We reached the middle of the string without finding a mismatch, so it is a palindrome.
  return true;
};
 
const str1 = 'Racecar';
const str2 = 'Hello, world!';
 
console.log(isPalindrome(str1)); // true
console.log(isPalindrome(str2)); // false

Time complexity

  • The time complexity is O(n) where n is the number of characters present in the string.

Space complexity

  • The space complexity is O(1) because we use constant space to store two indices.