A palindrome reads the same forward and backward. The brute-force approach - reverse the string and compare - allocates O(n) extra space for the reversed copy. Two pointers eliminate that waste entirely. Place one pointer at the start, one at the end, and walk them toward each other. If every pair of characters matches, the string is a palindrome. If any pair mismatches, it is not. You get O(n) time and O(1) space.

Why does this work? A palindrome is symmetric around its center. Checking from both ends simultaneously exploits that symmetry directly. You never need to see the full reversed string - you only need to verify that each mirror pair agrees.

The Basic Algorithm

The loop runs at most n/2 iterations. Each iteration does a constant-time character comparison and two pointer increments. When left meets or crosses right, every pair has matched and the string is confirmed as a palindrome.

For odd-length strings like "racecar", the middle character is its own mirror - the pointers never both land on it simultaneously because left < right fails before that happens. No special case needed.

Handling Real-World Input

Interview problems rarely give you clean lowercase strings. The classic "Valid Palindrome" problem asks you to ignore non-alphanumeric characters and treat uppercase and lowercase as equal. The two-pointer structure stays the same - you just add skip logic:

The inner while loops skip over spaces, punctuation, and other noise. The key detail is the left < right guard inside each inner loop - without it, skipping could push a pointer past the other, causing an out-of-bounds comparison.

Step through the palindrome check interactively and see how non-alphanumeric characters are skipped:

Time and Space Analysis

Each pointer moves at most n steps total across all iterations (including skips). The outer loop runs at most n/2 times. Inner skip loops collectively advance pointers at most n times total. This gives O(n) time. Space is O(1) - only two integer pointers regardless of input size.

Compare this to the reversal approach: return s == s[::-1] is one line of Python but allocates a full copy of the string. For a 10 MB string, that is 10 MB of wasted memory. The two-pointer approach uses the same 8 bytes of pointer storage whether the string is 10 characters or 10 million.

String reversal is one of the most common subroutines in string manipulation. On its own it is straightforward, but its real power emerges when used as a building block for more complex operations like word reversal, rotation, and rearrangement. The two-pointer approach reverses a string in-place with O(1) space.

In-Place Reversal

Place one pointer at the beginning, one at the end. Swap the characters at both pointers, then move them inward. Repeat until they meet or cross.

This performs exactly n/2 swaps. Each swap is O(1). Total time is O(n), space is O(1). The algorithm works identically for even and odd lengths - when the length is odd, the middle element stays in place because the pointers meet at it and the loop exits.

Watch the two pointers swap characters from both ends toward the center:

Reversing a Substring

A small but important generalization: reverse only a portion of the array between indices start and end. This is the core building block for word-by-word reversal.

Word-by-Word Reversal

The classic problem: given "the sky is blue", produce "blue is sky the". The elegant two-step approach uses reversal as a subroutine:

1. Reverse the entire string: "eulb si yks eht"
2. Reverse each individual word: "blue is sky the"

Why does this work? Reversing the whole string puts the words in the right order but each word is backward. Reversing each word individually fixes the letters within each word. Two reversals compose to give the desired result.

This runs in O(n) time - each character is swapped at most twice (once in the full reversal, once in the word reversal). Space is O(1) since everything happens in-place.

String Rotation via Reversal

To rotate a string left by k positions (move the first k characters to the end), apply three reversals:

For "abcdef" with k=2: reverse "ab" to get "bacdef", reverse "cdef" to get "bafedc", reverse the whole thing to get "cdefab". Three O(n) passes, O(1) space.

Partitioning rearranges elements so that all items satisfying a condition come before all items that do not. The two-pointer approach solves this in a single pass with O(1) extra space. This pattern is the backbone of quicksort's partition step, the Dutch National Flag problem, and many string filtering tasks.

The Boundary Pointer Pattern

The idea is simple: maintain a boundary pointer that tracks the "write position" - everything to its left satisfies the condition, everything at or to its right has not been processed yet. A scan pointer walks through the array. When it finds an element that satisfies the condition, swap it with the element at the boundary and advance the boundary.

After the loop, arr[0:boundary] contains all elements satisfying the condition, and arr[boundary:] contains the rest. The relative order within each group is preserved for the satisfying elements (this is a stable partition for the left group).

Example: Move Zeros to End

Given [0, 1, 0, 3, 12], move all zeros to the end while maintaining the relative order of non-zero elements.

Walk-through:

• i=0: value is 0, skip.
• i=1: value is 1, swap with index 0 → [1, 0, 0, 3, 12], boundary=1.
• i=2: value is 0, skip.
• i=3: value is 3, swap with index 1 → [1, 3, 0, 0, 12], boundary=2.
• i=4: value is 12, swap with index 2 → [1, 3, 12, 0, 0], boundary=3.

Result: [1, 3, 12, 0, 0]. Non-zero elements preserved their relative order. Zeros are at the end. One pass, O(n) time, O(1) space.

Partitioning Strings by Character Type

The same pattern works for strings stored as character arrays. Suppose you need to move all digits to the front of a string while keeping letters at the back:

This generalizes to any predicate: vowels before consonants, uppercase before lowercase, or any custom classification. The structure never changes - only the condition function varies.

Two-Way Partitioning from Both Ends

When you do not need to preserve relative order, you can partition faster by scanning from both ends simultaneously. This is the approach used in quicksort's Lomuto and Hoare partition schemes:

The left pointer finds elements that should be on the right side, the right pointer finds elements that should be on the left side, and they swap. This is not stable (relative order within groups is not preserved) but it touches fewer elements on average.

The read-write pointer pattern is a specialized two-pointer technique where one pointer scans input (the "reader" or "fast" pointer) and another builds output in-place (the "writer" or "slow" pointer). The reader always moves forward. The writer only advances when it writes a value. This creates an implicit partition: everything before the writer is the processed result, everything at or after the reader is unprocessed input.

This pattern solves three categories of problems: removing elements, deduplicating, and compressing - all in O(n) time with O(1) space.

Removing Duplicates from a Sorted Array

Given a sorted array, remove duplicates in-place and return the new length. The key insight: in a sorted array, duplicates are always adjacent. The writer stays at the last unique element. The reader scans ahead looking for the next different value.

Walk-through with [1, 1, 2, 2, 3]:

• reader=1: nums[1]=1 == nums[0]=1, skip.
• reader=2: nums[2]=2 != nums[0]=1, writer → 1, write 2.
• reader=3: nums[3]=2 == nums[1]=2, skip.
• reader=4: nums[4]=3 != nums[1]=2, writer → 2, write 3.
• Result: [1, 2, 3, _, _], return 3.

The writer only advances when a new unique value is found. Everything before writer+1 is the deduplicated result.

String Compression

Given ['a','a','b','b','b','c'], compress to ['a','2','b','3','c'] and return the new length. The reader scans consecutive groups, the writer records each character and its count.

The reader advances through each group of identical characters. The writer records the character once, then writes the count digits if the count exceeds 1. The writer never overtakes the reader because each group of k identical characters produces at most 1 + len(str(k)) characters of output, which is always less than or equal to k (since k >= 2 when we write the count).

Filtering Characters

Remove all occurrences of a target value from an array in-place:

The reader skips over elements equal to val. The writer copies everything else. This is the simplest form of the read-write pattern - a one-line condition determines whether the reader's current value gets written.

Why This Pattern Matters

The read-write pointer pattern is the in-place equivalent of building a new array with a filter or map operation. Where result = [x for x in arr if condition(x)] creates a new list in O(n) space, the read-write approach achieves the same result in O(1) space by overwriting the input array. In interviews, whenever a problem says "in-place" and "return the new length," the read-write pointer pattern is almost certainly the intended approach.

Practice

Apply the two-pointer patterns from this lesson to solve these problems: