Start learning free

LESSON 224 OF 347 · TWO POINTERS

Palindrome Check in C#: O(n) Time and O(1) Space with Two Pointers

Practice O(n) Read the full explanation

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward

Example 1:

Input:  "madam racecar madam"

Output: true

Example 2:

Input:  "abcbx"

Output: false

Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • s[0] == s[n - 1]
  • s[1] == s[n - 2]
  • s[2] == s[n - 3]
  • ...
How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers throught the algorithm?

For as long as i < j:
  • 1. We should check if s[i] != s[j] and if so, we conclude the string is not a palindrome and return false.
  • 2. Move i one step to the right.
  • 3. Move j one step to the left.
  • 4. Go to step 1.
If i became greater than or equal to j and we haven't returned false, then we can conclude the string is a palindrome and return true.

STEP 1 OF 6
    Ctrl + Enter to check

    C# · TWO POINTERS

    Palindrome Check in C#, explained

    Problem overview

    IsPalindrome takes a string input and returns a bool: true when the string reads the same forwards and backwards, false otherwise. The statement asks for O(n) time and O(1) extra space.

    "madam racecar madam" is a palindrome. The characters are compared one by one, including the spaces, and the first and last are both m, the second and second-to-last are both a, and so on. "abcbx" is not: its first character is a but its last is x.

    Approach

    The obvious solution reverses the string and compares it with the original. That works and is O(n) in time, but it builds a second string of n characters, so the extra space is O(n). The lesson asks for constant space, which rules it out.

    A string is a palindrome exactly when each character equals its mirror image: input[0] with input[n - 1], input[1] with input[n - 2], and so on. Two index variables can walk toward each other to check all those pairs in one pass without copying anything. left starts at the first index and right at the last. While left < right, compare the two characters. A mismatch settles the answer at once: the string is not a palindrome. A match means both pointers step inward.

    The loop stops when the pointers meet or cross. If the length is odd, the middle character has nothing to be compared with, which is fine because it is its own mirror. Reaching the end of the loop without a mismatch means every pair matched.

    Tracing a failure

    Take "abcbx", which has length 5. The pointers start at left = 0 and right = 4, and input[0] is a while input[4] is x. They differ, so the function returns false on the first comparison, without looking at the rest. Compare "abcba": the first pair a and a matches, the pointers move to 1 and 3, b matches b, and they move to 2 and 2. Now left < right is false, so the loop ends and the function returns true. The middle c is never compared, and it doesn't need to be.

    The number of comparisons is at most half the length, rounded down. A string of 1,000 characters needs 500 checks at most, and a string with a mismatch at the ends needs one.

    Step by step

    1. Create left as an int set to 0, the first index.
    2. Create right as an int set to input.Length - 1, the last index. Both must be variables because both change.
    3. Open a while loop with the condition left < right. While it holds, there is still an unchecked pair.
    4. Compare the pair. If input[left] != input[right], return false immediately.
    5. Move the pointers inward with left++ and right--. Without this the loop would check the same pair forever.
    6. Return true after the loop, since every pair matched.

    The solution in C#

    class Solution {
    public bool IsPalindrome(string input) {
        int left = 0;
        int right = input.Length - 1;
        while (left < right) {
            if (input[left] != input[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

    C# details:

    • Indexing a string gives a char. input[left] is a single UTF-16 character, and != on two char values compares them as characters. No conversion is needed, and no new string is created, which keeps the extra space constant.
    • Read-only access. Strings are immutable in C#, so you can read input[i] but never assign to it. That is no problem here because the algorithm only reads.
    • bool. The return type is bool, with the literals true and false in lowercase.
    • Length is a property. A string uses Length, not a method call: input.Length, not input.Length().

    C# char values are UTF-16 code units. For ordinary text this is exactly what you want. Characters outside the basic range, such as many emoji, take two code units, so a string like two identical emoji would be judged by code units rather than by visible characters. That doesn't matter for this lesson.

    Complexity

    Time: O(n). Each iteration moves the pointers one step closer, so the loop runs at most n/2 times, and each iteration does constant work. The early return can only make it faster.

    Space: O(1). The function stores two integers, whatever the length of the input.

    Edge cases and common mistakes

    • The empty string. right is -1, the loop condition is false at once, and the function returns true. An empty string reads the same in both directions.
    • One character. left and right are both 0, so the loop doesn't run and the answer is true.
    • Using left <= right. It also works, because it only adds a comparison of the middle character with itself. It is unnecessary though, so < is the usual choice.
    • Case and spaces count. "Aa" returns false because 'A' and 'a' are different characters, and "ab ba" is a palindrome only because of its middle space. Ignoring case or punctuation would be a different problem.
    • Forgetting to move a pointer. If only one of them moves, the pairs are no longer mirror images, and the answer is wrong.
    • Using input.Length as the last index. The last valid index is input.Length - 1. Starting at the length throws IndexOutOfRangeException.

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "" and "a" give true.
    • "Aa" gives false.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free