Start learning free

LESSON 244 OF 410 · TWO POINTERS

Palindrome Check in Java: 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 (the two-pointer approach below achieves this).


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • the character at index 0 equals the character at index n - 1
  • the character at index 1 equals the character at index n - 2
  • the character at index 2 equals the character at index 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 through the algorithm?

For as long as i < j:
  • 1. We should check if the characters at indices i and j are different, 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

    JAVA · TWO POINTERS

    Palindrome Check in Java, explained

    Problem overview

    A palindrome reads the same forward and backward. The method isPalindrome(String input) takes a string and returns true if it is one, false otherwise. Two examples:

    • "madam racecar madam" returns true. Reversing the whole string, spaces included, gives the same string back.
    • "abcbx" returns false. The first character is a and the last is x.

    The comparison is literal: every character counts, including spaces, punctuation and upper versus lower case. The lesson requires O(n) time and O(1) extra space.

    Approach: compare from both ends with two pointers

    A string is a palindrome exactly when its first character equals its last, its second equals its second-to-last, and so on. In index terms, input.charAt(k) must equal input.charAt(n - 1 - k) for every k, where n is the length.

    The simplest way to check that is two index variables. left starts at the first character and right at the last. While they have not met, compare the two characters, then move both one step toward the middle. A single mismatch settles the answer as false immediately. If the pointers meet without a mismatch, every pair matched.

    The common alternative is to build the reversed string and compare it with the original:

    static boolean isPalindromeReversed(String input) {
    return new StringBuilder(input).reverse().toString().equals(input);
}

    It is correct and short, but it creates a second string as long as the first, so it uses O(n) extra space and always looks at every character. The two-pointer version allocates nothing and can stop at the first mismatch, which is why the lesson asks for it.

    Step by step

    1. Create left as an int set to 0. It will move, so it is a variable and not a constant.
    2. Create right as an int set to input.length() - 1. Indices start at 0, so the last valid index is one less than the length. Note that length() has parentheses for a String; for an array it would be the field length.
    3. Loop while left < right. When the pointers meet or cross, there is no pair left to compare. For a string of odd length, the middle character is never compared, which is fine because it is its own mirror image.
    4. Return false on a mismatch. Compare input.charAt(left) with input.charAt(right).
    5. Move the pointers. Increment left and decrement right at the end of each pass. Without this the loop would compare the same pair forever.
    6. Return true after the loop. The code can only get there if no pair differed.

    The solution in Java

    class Solution {
    public boolean isPalindrome(String input) {
        int left = 0;
        int right = input.length() - 1;
        while (left < right) {
            if (input.charAt(left) != input.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

    Java details that matter here:

    • charAt returns a char, a primitive. So != compares the characters themselves, which is exactly what is wanted. This is different from strings and other objects, where == and != compare references and you must call equals.
    • charAt is O(1). A Java String is backed by an array, so reading a position does not walk the string. That is what keeps the loop linear.
    • The empty string is a palindrome. Its length is 0, so right starts at -1, the loop condition is false at once, and the method returns true. A one-character string behaves the same way, because left and right are both 0.

    Time and space complexity

    Each pass of the loop moves the pointers one step closer, so the loop runs at most n / 2 times. That is O(n) time in the worst case, which happens when the string is a palindrome or differs only near the middle. When the first and last characters differ, the method returns after one comparison. The extra memory is two int variables, which is O(1) space.

    Edge cases and common mistakes

    • Upper and lower case. This solution is case-sensitive, so "Madam" returns false because M and m are different characters. To ignore case, compare Character.toLowerCase(input.charAt(left)) with the lower-cased right character, or call input.toLowerCase() first.
    • Spaces and punctuation. They are compared like any other character. A phrase such as "A man, a plan" is not a palindrome here. The version that skips non-letters moves each pointer past characters that Character.isLetterOrDigit rejects before comparing.
    • Looping to the end of the string. A loop like for (int i = 0; i < input.length(); i++) that compares with the mirror position works, but does every comparison twice. Stopping at the middle is enough.
    • Off-by-one on the right pointer. Starting right at input.length() makes the first charAt throw StringIndexOutOfBoundsException.
    • null. Calling input.length() on a null reference throws NullPointerException. The lesson passes real strings, but production code would check for null first.

    Checking a number

    The same method checks whether an integer is a palindrome: convert it with String.valueOf and reuse the check. For example 121 gives "121", which is a palindrome, and 123 is not. A negative number such as -121 becomes "-121", which reads 121- backward, so it is not one.

    Testing

    Good inputs to try: "" and "a" (both true), "ab" (false), "abba" (even length, true), "abcba" (odd length, true) and "abca" (the ends match but the middle does not, false).

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free