Data Structures · Array

Palindrome Check

The idea

Fold a paper strip with numbers written on it exactly in half. If every number lands on an identical twin, the strip reads the same from both directions. Checking is the fold: match the outermost pair, then the next pair in, working toward the crease.

The problem

Does the array read the same forwards and backwards? You could build a reversed copy and compare — but that costs a whole extra array. The two-pointer way needs no copy: compare the first element with the last, the second with the second-to-last, and walk inward. One mismatch anywhere settles it instantly.

Why it's slow

At most n/2 comparisons — each one checks a mirrored pair, and half the pairs cover the whole array. The early exit is the interview point: a mismatch at the very first pair answers NO after one comparison. The worst case is when the answer is YES, because proving a palindrome means every single pair must be checked.

Pseudocode

  1. put one pointer at each end
    Explain this line

    Mirror positions pair up: first with last, second with second-to-last.

  2. while the pointers have not crossed
    Explain this line

    Once the pointers meet or cross, every mirrored pair has been examined.

  3. compare the two values they point at
    Explain this line

    One comparison per pair — the value at lo against the value at hi.

  4. if they differ, stop — not a palindrome
    Explain this line

    A single mismatch is a complete answer: no palindrome, stop immediately.

  5. matched: move both pointers inward
    Explain this line

    A matched pair is verified — both positions are done; the pointers step inward.

  6. every pair matched — it is a palindrome
    Explain this line

    No pair disagreed, so the array mirrors perfectly. An odd middle element needs no check — it faces itself.

Complexity

Best Average Worst Space
O(1) O(n) O(n) O(1)

Best case: first pair differs, one comparison. Worst case is a true palindrome — all n/2 pairs must be verified. No extra array needed.

Code

python 
def is_palindrome(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        if a[lo] != a[hi]:
            return False
        lo += 1
        hi -= 1
    return True
java 
static boolean isPalindrome(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        if (a[lo] != a[hi]) return false;
        lo++;
        hi--;
    }
    return true;
}
cpp 
bool isPalindrome(const std::vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        if (a[lo] != a[hi]) return false;
        ++lo;
        --hi;
    }
    return true;
}
javascript 
function isPalindrome(a) {
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    if (a[lo] !== a[hi]) return false;
    lo++;
    hi--;
  }
  return true;
}
dart 
bool isPalindrome(List<int> a) {
  var lo = 0, hi = a.length - 1;
  while (lo < hi) {
    if (a[lo] != a[hi]) return false;
    lo++;
    hi--;
  }
  return true;
}

Quick check