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

Time Complexity: Valid Palindrome Two Pointer

O(n)

Understanding Time Complexity

We want to know how the time 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 input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool isPalindrome(char * s) {
    int left = 0, right = strlen(s) - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
    

This code checks if a string reads the same forwards and backwards using two pointers moving towards the center.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters at left and right pointers.
• How many times: Up to n/2 times, where n is the string length.

How Execution Grows With Input

As the string gets longer, the number of comparisons grows roughly half as fast.

Input Size (n)	Approx. Operations
10	5 comparisons
100	50 comparisons
1000	500 comparisons

Pattern observation: The steps grow linearly with input size, about half the length.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows directly with the string length.

Common Mistake

[X] Wrong: "The two-pointer method checks every character twice, so it is O(2n)."

[OK] Correct: Each character is checked only once in a pair, so the total checks are about n/2, which simplifies to O(n).

Interview Connect

Understanding this linear time check helps you quickly validate strings in many problems, showing you can write efficient, clear code.

Self-Check

"What if we ignored non-alphanumeric characters and spaces? How would the time complexity change?"