Valid Palindrome Two Pointer in DSA Typescript

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.

s = "r a c e c a r"
left ↑                 right ↑

Dry Run Walkthrough

Input: string: "racecar"

Goal: Determine if the string reads the same forwards and backwards

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

r [left->r] a c e c a [right->r]

Why: Check if outer characters match to confirm palindrome property

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

r a [left->a] c e c [right->a] r

Why: Continue checking inward pairs for equality

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

r a c [left->c] e [right->c] a r

Why: Still matching pairs, palindrome check continues

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

r a c e [left->e,right->e] c a r

Why: Middle reached, all pairs matched so far

Result:

r a c e c a r
Palindrome check passed: true

Annotated Code

DSA Typescript

class Solution {
  isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
      if (s[left] !== s[right]) {
        return false; // mismatch found, not palindrome
      }
      left++; // move inward from left
      right--; // move inward from right
    }
    return true; // all pairs matched
  }
}

// Driver code
const sol = new Solution();
const input = "racecar";
const result = sol.isPalindrome(input);
console.log(`${input} is palindrome: ${result}`);

if (s[left] !== s[right]) {

Check if characters at current pointers differ to detect non-palindrome

left++;

Advance left pointer inward to next character

right--;

Advance right pointer inward to previous character

return true;

If all pairs matched, confirm string is palindrome

Output

racecar is palindrome: true

Complexity Analysis

Time: O(n) because we compare pairs of characters moving inward once through the string

Space: O(1) because only two pointers are used regardless of input size

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

Edge Cases

empty string

returns true since empty string reads same forwards and backwards

DSA Typescript

while (left < right) {

single character string

returns true since single character is palindrome

DSA Typescript

while (left < right) {

string with mismatch early

returns false immediately when first mismatch found

DSA Typescript

if (s[left] !== s[right]) {

When to Use This Pattern

When asked if a string reads the same forwards and backwards, use two pointers from both ends to compare characters efficiently.

Common Mistakes

Mistake: Not moving both pointers inward after a successful match
Fix: Increment left and decrement right pointers inside the loop after confirming characters match

Mistake: Using <= instead of < in loop condition causing unnecessary comparison of middle character
Fix: Use while (left < right) to avoid redundant middle character check

Summary

Checks if a string is the same forwards and backwards by comparing characters from both ends.

Use when you need to verify palindrome property efficiently without extra space.

The key insight is to use two pointers moving inward to compare pairs step-by-step.

Practice

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

easy

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

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

C. Use two pointers starting at both ends and move towards the center comparing characters

D. Sort the characters and check if the sorted string equals the original

Solution

1. Step 1: Understand 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; otherwise, it's not a palindrome.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Reversing string instead of using pointers
• Checking only half the string without pointers
• Ignoring case or non-alphanumeric characters

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

easy

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

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

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

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

Solution

1. Step 1: Identify pointer positions

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

2. Step 2: Check code correctness

   let left = 0; let right = s.length - 1; correctly sets left = 0 and right = s.length - 1, valid indices for string.

3. Final Answer:

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

4. Quick Check:

   Pointers start at 0 and length-1 = let left = 0; let 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)
• Starting left pointer at 1 instead of 0
• Confusing length with last index

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

function isPalindrome(s: string): boolean {
  let left = 0;
  let 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 'racecar' input

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

2. Step 2: Trace 'hello' input

   Characters 'h' and 'o' differ at ends, returns false immediately.

3. Final Answer:

   true false -> Option A

4. Quick Check:

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

Hint: Check characters from ends; mismatch means false [OK]

Common Mistakes:

• Assuming 'hello' is palindrome
• Returning true without checking all pairs
• Off-by-one errors in pointer movement

4. Identify the bug in this TypeScript palindrome checker:

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

medium

A. left pointer should start at 1

B. right pointer initialized to s.length instead of s.length - 1

C. Comparison should be s[left] === s[right]

D. Loop condition should be left <= right

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: Understand impact of bug

   Accessing s[s.length] causes undefined comparison or runtime error.

3. Final Answer:

   right pointer initialized to s.length instead of s.length - 1 -> Option B

4. Quick Check:

   Right pointer must be last index = length-1 [OK]

Hint: Right pointer must be last index, not length [OK]

Common Mistakes:

• Using s.length as index causes out-of-bounds
• Changing loop condition incorrectly
• Confusing equality and inequality in comparison

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

hard

A. Convert string to uppercase and compare all characters

B. Reverse the string and compare directly

C. Only compare characters at even indices

D. Ignore case and skip non-alphanumeric characters during comparison

Solution

1. Step 1: Understand input complexity

   String contains spaces, commas, and mixed case letters which must be ignored for palindrome check.

2. Step 2: Modify two-pointer logic

   Skip non-alphanumeric characters and compare characters case-insensitively while moving pointers inward.

3. Final Answer:

   Ignore case and skip non-alphanumeric characters during comparison -> Option D

4. Quick Check:

   Skip non-letters and ignore case for valid palindrome [OK]

Hint: Skip non-letters and compare lowercase chars [OK]

Common Mistakes:

• Comparing characters without ignoring punctuation
• Not converting characters to same case
• Assuming direct comparison works on raw string