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

Time Complexity: Valid Palindrome Two Pointer

O(n)

Understanding Time Complexity

We want to know how the time taken 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.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    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 two positions in the string.
• How many times: At most, half the length of the string (n/2) times.

How Execution Grows With Input

As the string length grows, 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 number of steps grows linearly with input size, but only half as many checks are needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows directly in proportion to the string length.

Common Mistake

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

[OK] Correct: The method compares pairs from both ends simultaneously, so it only needs about n/2 comparisons, which is still O(n) because constants are ignored.

Interview Connect

Understanding this simple linear time check helps build confidence for string problems and shows you can reason about efficient scanning techniques.

Self-Check

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