Valid Palindrome Two Pointer in DSA Typescript - Execution Trace

Concept Flow - Valid Palindrome Two Pointer

Start with left=0, right=length-1

↓

Check if left < right?

No→Done: Palindrome

Yes↓

Is s[left

Yes↓

Is s[right

Yes↓

Compare s[left

↓

left = left + 1, right = right - 1

↩Back to Check

Two pointers start at the string ends, skip non-alphanumeric chars, compare characters ignoring case, move inward if equal, else return false.

Execution Sample

DSA Typescript

function isAlphaNum(c: string): boolean {
  return /^[a-z0-9]$/i.test(c);
}

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

Checks if a string is a palindrome ignoring non-alphanumeric characters and case using two pointers.

Execution Table

Step	Operation	left	right	Characters Compared	Action	Result
1	Initialize pointers	0	10	-	Start	Continue
2	Check s[left]='A' alphanumeric?	0	10	-	Yes	Continue
3	Check s[right]='a' alphanumeric?	0	10	-	Yes	Continue
4	Compare 'A' and 'a'	0	10	'A' vs 'a'	Equal (case-insensitive)	Move inward
5	Update pointers	1	9	-	left++ and right--	Continue
6	Check s[left]=' ' alphanumeric?	1	9	-	No	left++
7	Update pointers	2	9	-	left++	Continue
8	Check s[left]='m' alphanumeric?	2	9	-	Yes	Continue
9	Check s[right]='M' alphanumeric?	2	9	-	Yes	Continue
10	Compare 'm' and 'M'	2	9	'm' vs 'M'	Equal (case-insensitive)	Move inward
11	Update pointers	3	8	-	left++ and right--	Continue
12	Check s[left]='a' alphanumeric?	3	8	-	Yes	Continue
13	Check s[right]='a' alphanumeric?	3	8	-	Yes	Continue
14	Compare 'a' and 'a'	3	8	'a' vs 'a'	Equal	Move inward
15	Update pointers	4	7	-	left++ and right--	Continue
16	Check s[left]='n' alphanumeric?	4	7	-	Yes	Continue
17	Check s[right]='n' alphanumeric?	4	7	-	Yes	Continue
18	Compare 'n' and 'n'	4	7	'n' vs 'n'	Equal	Move inward
19	Update pointers	5	6	-	left++ and right--	Continue
20	Check s[left]='a' alphanumeric?	5	6	-	Yes	Continue
21	Check s[right]='a' alphanumeric?	5	6	-	Yes	Continue
22	Compare 'a' and 'a'	5	6	'a' vs 'a'	Equal	Move inward
23	Update pointers	6	5	-	left++ and right--	Continue
24	Check left < right?	6	5	-	No	End loop
25	Return	-	-	-	-	True (Palindrome)

💡 Pointers crossed (left=6, right=5), all compared characters matched ignoring case and non-alphanumeric skipped.

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 11	After Step 15	After Step 19	After Step 23	Final
left	0	1	2	3	4	5	6	6
right	10	9	9	8	7	6	5	5

Key Moments - 3 Insights

Why do we skip characters that are not alphanumeric instead of comparing them?

Because the palindrome check ignores spaces and punctuation. As shown in steps 6 and 7, the left pointer moves past a space without comparison.

Why do we compare characters in lowercase?

To ignore case differences. For example, in step 4, 'A' and 'a' are considered equal after converting both to lowercase.

Why does the loop stop when left >= right?

Because all character pairs have been checked. When pointers cross (step 24), it means the string is a palindrome.

Visual Quiz - 3 Questions

Look at the execution table at step 6, what happens to the left pointer?

A It stays the same

B It moves forward by 1

C It moves backward by 1

D It moves to the right pointer position

💡 Hint

Check the 'Action' and 'left' columns at step 6 in the execution_table.

At which step do the pointers cross, ending the palindrome check?

A Step 22

B Step 24

C Step 20

D Step 18

💡 Hint

Look for the step where 'Check left < right?' is 'No' in the execution_table.

If the string had a non-alphanumeric character at the right pointer, what would happen according to the execution flow?

A Right pointer moves left by 1 without comparison

B Left pointer moves right by 1 without comparison

C Both pointers move inward by 1

D Function returns false immediately

💡 Hint

Refer to the concept_flow where non-alphanumeric at right causes right--.

Concept Snapshot

Valid Palindrome Two Pointer
- Use two pointers: left at start, right at end
- Skip non-alphanumeric chars
- Compare characters ignoring case
- Move pointers inward if equal
- Return false if mismatch found
- Return true if pointers cross

Full Transcript

This concept uses two pointers starting at the ends of the string. We skip characters that are not letters or numbers. We compare the characters ignoring uppercase or lowercase differences. If they match, we move the pointers inward. If they don't match, we return false. When the pointers cross, it means the string is a palindrome. The execution table shows each step of pointer movement and comparison. The variable tracker shows how left and right pointers change. Key moments clarify why we skip non-alphanumeric characters, why we compare lowercase, and why the loop ends when pointers cross.

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