Why check palindrome symmetry with two inward-walking indices instead of reversing the text?

## What the check actually asserts A sequence is a palindrome when the character at position `i` equals the character at position `n-1-i` for every `i`. That is a statement about **mirrored pairs**, and it is worth saying out loud in an interview, because every implementation is just a different way of testing the same set of pairs. There are `floor(n/2)` such pairs; the middle character of an odd-length input is paired with itself and is trivially satisfied. A concrete setting: a ticket-code validator that must accept only codes that read the same in both directions. Codes arrive as short mixed-case text with separators in them, and the validator runs on every scan at a gate, so both correctness and memory behaviour matter. ## The inward scan ``` lo = 0 hi = length(s) - 1 while lo < hi: if s[lo] != s[hi]: return false lo = lo + 1 hi = hi - 1 return true ``` Each iteration tests exactly one mirrored pair and then shrinks the unchecked window from both sides. The loop runs at most `floor(n/2)` times, so the work is O(n) — halving the number of iterations does not change the asymptotic class, it changes the constant. Auxiliary space is O(1): two integers, regardless of input size. **Why `lo < hi` and not `lo <= hi`.** With `<=`, an odd-length input performs one extra iteration in which `lo == hi` and the character is compared with itself — never a mismatch, just a wasted comparison. More importantly, `<` is what makes the degenerate inputs correct without special cases. For an empty input, `hi` starts at `-1`, the condition is false immediately, and the answer is `true`. For a single character, `lo == hi == 0`, the loop is skipped, and the answer is `true`. Both are palindromes under the standard definition — they read identically in both directions — and a candidate who hand-writes special cases for them has usually not noticed that the bound already handles them. ## Reverse and compare The alternative builds the reversed sequence and tests it for equality with the original. It is easy to state and easy to get right, and it is also O(n) time. What it costs is O(n) auxiliary space: a second buffer of the same length. On a gate validator processing short codes that is irrelevant; on a service scanning multi-megabyte inputs, doubling peak memory per in-flight request is a real capacity decision. The second, smaller difference is **early exit**. The inward scan can reject after one comparison when the first and last characters disagree, which is the common case for random non-palindromic input. Reverse-then-compare does the whole reversal first, then compares — and while a careful equality test also short-circuits, the reversal work has already been paid. Neither behaviour changes the O(n) upper bound: big-O is an upper bound on the worst case, and the worst case for both is a genuine palindrome, where every pair must be examined. ## The normalization wrinkle Real validators rarely compare raw characters. If the spec says separators and punctuation are ignored, the scan advances whichever index currently sits on an ignorable character before comparing: - advance `lo` while `lo < hi` and `s[lo]` is ignorable; - advance `hi` while `lo < hi` and `s[hi]` is ignorable; - then compare, applying whatever case rule the spec states. The `lo < hi` guard on each advance matters: an input made entirely of separators would otherwise walk an index off the end. Done this way the scan still costs O(n) time and O(1) space, because no filtered copy is ever built — which is precisely the advantage that disappears if you "clean" the input into a new buffer first and then reverse it, paying two copies instead of none. ## What interviewers are listening for They want the pair invariant stated, the space difference named rather than hand-waved as "the same complexity", the loop bound justified, and the two degenerate inputs answered without hesitation. A candidate who says "both are O(n), so it does not matter" has confused time complexity with resource behaviour; a candidate who cannot say whether an empty input is a palindrome has not thought about the bound at all.