Start learning free

LESSON 248 OF 414 · TWO POINTERS

Palindrome Check in Scala: Two Pointers in O(n) Time and O(1) Space

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

    SCALA · TWO POINTERS

    Palindrome Check in Scala, explained

    Problem overview

    The method isPalindrome receives a string input and returns true when the string reads the same forwards and backwards, and false otherwise. The lesson asks for O(n) time and O(1) extra space.

    For "madam racecar madam" the answer is true: the spaces are characters like any other, and the whole string is its own mirror image. For "abcbx" the answer is false, because the first character a doesn't match the last one, x.

    Approach: compare the two ends and move inward

    A string is a palindrome when the first character equals the last, the second equals the second to last, and so on. That is the whole test. A tempting shortcut is to build a reversed copy of the string and compare it with the original. It is correct, but it uses O(n) extra memory, which the lesson rules out.

    Instead, keep two indices: left at the first character and right at the last one. Compare the two characters they point to. If they differ, the string cannot be a palindrome, so stop with false. If they match, move left one step right and right one step left, and repeat. When the pointers meet or cross, every pair has been checked, and the answer is true.

    Take "abcbx". The first comparison, positions 0 and 4, is a against x, and the method returns false immediately. For "abcba" the pairs are a/a and b/b, then the pointers both reach position 2 and the loop ends: the answer is true.

    Step by step

    1. Create the left pointer as a var named left, starting at 0. It must be a var because it changes as the loop runs.
    2. Create the right pointer as a var named right, starting at input.length - 1. Indices start at 0, so the last one is one less than the length.
    3. Loop while left < right. As long as the pointers haven't met, there is still a pair to compare. With an odd length, the middle character is never compared; it matches itself, so skipping it is correct.
    4. Compare the pair. Inside the loop, test input(left) != input(right). On a mismatch, return false at once: one bad pair is enough.
    5. Move the pointers. After the if, add 1 to left and subtract 1 from right. Without this, the loop would compare the same pair forever.
    6. Return true after the loop. Reaching this line means no pair failed.

    The solution in Scala

    class Solution {
    def isPalindrome(input: String): Boolean = {
        var left = 0
        var right = input.length - 1
        while (left < right) {
            if (input(left) != input(right)) {
                return false
            }
            left += 1
            right -= 1
        }
        return true
    }
}

    The Scala details worth a closer look:

    • Indexing a string. Scala reads the character at a position with parentheses: input(left). Square brackets are used for type parameters in Scala, not for indexing.
    • Char comparison. input(left) is a Char, and != compares the two characters by value. Uppercase and lowercase letters are different characters, so "Madam" is not a palindrome here.
    • return inside a while loop. A while loop is part of the method body, so return false exits the method directly. return is used rarely in Scala, but it is fine in this position.
    • left += 1 is shorthand for left = left + 1. It works because left is a var.
    • Parameters are fixed. input is a method parameter and can't be reassigned, and a Scala String is immutable. Nothing is copied or changed; the loop only reads characters.

    Other ways to write it

    Scala can compare a string with its reversed copy directly:

    val input = "madam racecar madam"
println(input == input.reverse) // true

    This is short and correct, but it creates a second string of the same length, so it uses O(n) extra space. The two-pointer loop avoids that, which is the point of this lesson.

    If a version of the problem ignored case, spaces and punctuation, the string would have to be cleaned before the check:

    val text = "A man, a plan, a canal: Panama"
val cleaned = text.filter(_.isLetterOrDigit).toLowerCase
println(cleaned)                    // amanaplanacanalpanama
println(cleaned == cleaned.reverse) // true
println(text == text.reverse)       // false

    This lesson compares characters exactly as they are.

    Complexity

    Time: O(n). Each iteration moves the pointers closer by two positions, so the loop runs at most n / 2 times, with a constant amount of work in each.

    Space: O(1). The method uses two integers and never builds a new string.

    Edge cases and common mistakes

    • Empty string. right starts at -1, so left < right is false and the method returns true. An empty string reads the same in both directions.
    • One character. Both pointers are 0, the loop never runs, and the result is true.
    • Even length. "abba" compares a/a and b/b, then the pointers cross. The result is true; "ab" is false.
    • Spaces and case. The method compares characters exactly. "a man a plan" is false, and "Madam" is false because M and m differ. The lesson's tests need no special handling for either.
    • Using left <= right. It also works, since the last comparison would be a character with itself, but it does one needless step.
    • Forgetting to move a pointer. The loop would never end for a palindrome, because the same pair would match again and again.
    • Starting right at input.length. That index is one past the end, and reading it throws a StringIndexOutOfBoundsException.

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "" gives true.
    • "a" gives true.
    • "ab" gives false.
    • "abba" gives true.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free