Valid Palindrome Two Pointer in DSA Javascript - Time & Space Complexity

Time Complexity: Valid Palindrome Two Pointer

O(n)

Understanding Time Complexity

We want to know how the time needed to check if a string is a palindrome grows as the string gets longer.

Specifically, how many steps does the two-pointer method take as the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code checks if a string is a palindrome by moving two pointers from the ends towards the center, skipping non-alphanumeric characters.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves two pointers from the start and end towards the middle.
• How many times: Each character is visited at most once by either pointer, so up to n times where n is the string length.

How Execution Grows With Input

As the string gets longer, the number of steps grows roughly in a straight line with the string length.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The steps increase directly with input size, doubling the input roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows in a straight line with the length of the string.

Common Mistake

[X] Wrong: "Because there are nested while loops, the time must be quadratic O(n²)."

[OK] Correct: The inner loops only skip non-alphanumeric characters and each character is visited once total, so the total work is still linear.

Interview Connect

Understanding this linear time check shows you can analyze pointer-based string algorithms clearly, a useful skill for many coding challenges.

Self-Check

"What if we removed the checks that skip non-alphanumeric characters? How would the time complexity change?"

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