Valid Palindrome Two Pointer in DSA Javascript

Mental Model

Check if a word reads the same forwards and backwards by comparing letters from both ends moving towards the center.

Analogy: Imagine two friends starting at opposite ends of a line of people, checking if each pair of people look the same until they meet in the middle.

h -> e -> l -> l -> o
↑                 ↑
left             right

Dry Run Walkthrough

Input: string: 'racecar'

Goal: Determine if 'racecar' is a palindrome by comparing characters from both ends.

Step 1: Compare characters at left=0 and right=6 ('r' and 'r')

r -> a -> c -> e -> c -> a -> r
↑                       ↑

Why: Start by checking the first and last characters to see if they match.

Step 2: Move left to 1 and right to 5, compare 'a' and 'a'

r -> a -> c -> e -> c -> a -> r
    ↑             ↑

Why: Since previous characters matched, check next inner pair.

Step 3: Move left to 2 and right to 4, compare 'c' and 'c'

r -> a -> c -> e -> c -> a -> r
        ↑       ↑

Why: Continue moving inward to verify matching characters.

Step 4: Move left to 3 and right to 3, compare 'e' and 'e'

r -> a -> c -> e -> c -> a -> r
            ↑

Why: Pointers meet in the middle, last character to check.

Result:

r -> a -> c -> e -> c -> a -> r
Palindrome: true

Annotated Code

DSA Javascript

class Solution {
  isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
      while (left < right && !this.isAlphaNumeric(s[left])) {
        left++;
      }
      while (left < right && !this.isAlphaNumeric(s[right])) {
        right--;
      }
      if (s[left].toLowerCase() !== s[right].toLowerCase()) {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }

  isAlphaNumeric(c) {
    return /[a-z0-9]/i.test(c);
  }
}

const sol = new Solution();
console.log(sol.isPalindrome('racecar'));

while (left < right) {

loop until pointers meet or cross

while (left < right && !this.isAlphaNumeric(s[left])) { left++; }

skip non-alphanumeric from left

while (left < right && !this.isAlphaNumeric(s[right])) { right--; }

skip non-alphanumeric from right

if (s[left].toLowerCase() !== s[right].toLowerCase()) { return false; }

compare characters ignoring case, return false if mismatch

left++; right--;

move pointers inward to next characters

Output

true

Complexity Analysis

Time: O(n) because we scan the string once with two pointers moving inward

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to reversing the string and comparing, this uses less space and can stop early on mismatch

Edge Cases

empty string

returns true because empty string reads the same forwards and backwards

DSA Javascript

while (left < right) {

string with only non-alphanumeric characters

skips all characters and returns true

DSA Javascript

while (left < right && !this.isAlphaNumeric(s[left])) { left++; }

string with mixed case and punctuation, e.g. 'A man, a plan, a canal: Panama'

ignores case and punctuation, returns true if palindrome

DSA Javascript

if (s[left].toLowerCase() !== s[right].toLowerCase()) { return false; }

When to Use This Pattern

When you need to check if a string reads the same forwards and backwards ignoring spaces and punctuation, use the two pointer palindrome pattern for efficient checking.

Common Mistakes

Mistake: Not skipping non-alphanumeric characters causing false negatives
Fix: Add checks to skip non-alphanumeric characters before comparing

Mistake: Comparing characters without ignoring case
Fix: Convert characters to lowercase before comparison

Summary

Checks if a string is a palindrome by comparing characters from both ends moving inward.

Use when you want to verify palindrome property efficiently ignoring non-letters and case.

The key insight is to use two pointers moving inward and skip irrelevant characters.

Practice

1. What is the main idea behind the two-pointer technique to check if a string is a palindrome?

easy

A. Use two pointers starting from both ends and move towards the center comparing characters

B. Reverse the string and compare it with the original string

C. Count the frequency of each character and check if all are even

D. Sort the string and check if it matches the original

Solution

1. Step 1: Understand the two-pointer approach

   Two pointers start at the beginning and end of the string and move inward.

2. Step 2: Compare characters at pointers

   If characters at both pointers match, move pointers closer; if not, string is not palindrome.

3. Final Answer:

   Use two pointers starting from both ends and move towards the center comparing characters -> Option A

4. Quick Check:

   Two-pointer technique = Use two pointers starting from both ends and move towards the center comparing characters [OK]

Hint: Compare characters from both ends moving inward [OK]

Common Mistakes:

• Trying to reverse the string instead of using pointers
• Checking only half the string without comparing both ends
• Ignoring case or non-alphanumeric characters

2. Which of the following JavaScript code snippets correctly initializes two pointers for palindrome checking?

easy

A. let left = s.length - 1, right = 0;

B. let left = 1, right = s.length;

C. let left = s.length, right = 0;

D. let left = 0, right = s.length - 1;

Solution

1. Step 1: Identify correct pointer initialization

   Left pointer should start at 0 (start of string), right pointer at last index (length - 1).

2. Step 2: Check each option

   let left = 0, right = s.length - 1; correctly sets left=0 and right=s.length-1; others have incorrect indices.

3. Final Answer:

   let left = 0, right = s.length - 1; -> Option D

4. Quick Check:

   Start pointers at 0 and length-1 = let left = 0, right = s.length - 1; [OK]

Hint: Start left at 0 and right at length minus one [OK]

Common Mistakes:

• Setting right pointer to s.length (out of bounds)
• Swapping left and right pointers
• Starting left pointer at 1 instead of 0

3. What will be the output of the following code?

function isPalindrome(s) {
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}
console.log(isPalindrome('racecar'));
console.log(isPalindrome('hello'));

medium

A. true false

B. false true

C. true true

D. false false

Solution

1. Step 1: Trace isPalindrome('racecar')

   Characters match from both ends moving inward, so returns true.

2. Step 2: Trace isPalindrome('hello')

   Characters at start and end differ ('h' vs 'o'), returns false immediately.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   'racecar' palindrome = true, 'hello' not palindrome = false [OK]

Hint: Check characters from ends; stop at first mismatch [OK]

Common Mistakes:

• Assuming 'hello' is palindrome
• Not returning false immediately on mismatch
• Confusing return values order

4. Find the error in this palindrome check code:

function isPalindrome(s) {
  let left = 0, right = s.length;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

medium

A. The while condition should be left <= right

B. Left pointer should start at 1, not 0

C. Right pointer should start at s.length - 1, not s.length

D. The function should return false at the end

Solution

1. Step 1: Check pointer initialization

   Right pointer is set to s.length, which is out of string index range (0 to length-1).

2. Step 2: Correct pointer initialization

   Right pointer should be s.length - 1 to point to last character.

3. Final Answer:

   Right pointer should start at s.length - 1, not s.length -> Option C

4. Quick Check:

   Right pointer = length - 1 [OK]

Hint: Right pointer must be last index (length - 1) [OK]

Common Mistakes:

• Using s.length as index causes undefined access
• Changing left pointer start incorrectly
• Incorrect loop condition causing infinite loop

5. Given the string s = 'A man, a plan, a canal: Panama', which modification to the two-pointer palindrome check is needed to correctly identify it as a palindrome?

hard

A. Reverse the string and compare directly

B. Ignore non-alphanumeric characters and compare characters case-insensitively

C. Only check the first half of the string

D. Convert the string to uppercase and compare characters directly

Solution

1. Step 1: Understand the input string

   The string contains spaces, commas, and mixed cases which should be ignored for palindrome check.

2. Step 2: Modify two-pointer approach

   Skip non-alphanumeric characters and compare characters in lowercase to handle case differences.

3. Final Answer:

   Ignore non-alphanumeric characters and compare characters case-insensitively -> Option B

4. Quick Check:

   Clean and lowercase string before comparing [OK]

Hint: Skip symbols and compare lowercase letters only [OK]

Common Mistakes:

• Comparing characters without ignoring symbols
• Not handling uppercase vs lowercase differences
• Assuming direct comparison works on raw string