Two Pointers on Strings
Scenario
You need to reverse a massive string or sanitize it of leading/trailing spaces in an embedded C system with strict memory limits.
How do you manipulate the string without allocating any new memory buffers?
Why it exists
Problem: Naive string operations (reversing, filtering) typically allocate entirely new string buffers, costing O(N) auxiliary memory. This is unacceptable in low-memory environments.
Naive approach: Create a new empty array, iterate backward through the input, and copy elements over one by one.
Better idea: Place two integer pointers (indices) at opposite ends of the string. Swap their values, then move them inward. This modifies the data in-place using O(1) auxiliary space.
Mental model
Imagine holding the two opposite ends of a string of beads. You swap the beads in your hands, then move your hands one bead closer to the center, and swap again. You stop when your hands touch.
The Two-Pointer technique uses two indices traversing the data structure simultaneously. For strings, they usually converge from opposite ends (to reverse or validate symmetry) or move in the same direction at different speeds (to filter data).
Repeated decision: Does the pair of characters at the left and right pointers satisfy the condition? If so, process and move inward.
Explanation
To reverse an array of characters in-place, initialize `left = 0` and `right = length - 1`.
While `left < right`:
1. Swap the character at `left` with the character at `right`.
2. Increment `left` by 1 (moving inward).
3. Decrement `right` by 1 (moving inward).
The loop terminates exactly when the pointers cross in the middle. The algorithm touches every element exactly once, taking O(N) time, but requires literally zero extra memory allocations (O(1) space).
This paradigm isn't just for swapping; it handles complex conditional logic. If you need to reverse only the vowels in a string, the `left` pointer moves right until it finds a vowel, the `right` pointer moves left until it finds a vowel, and then they swap. The core invariant remains: everything outside the [left, right] boundary is completely finalized.
Key points
- O(N) Time: The pointers only move inward, evaluating each character at most once.
- O(1) Auxiliary Space: All operations occur directly on the existing character array.
- Convergence Boundary: The loop condition `left < right` mathematically guarantees that pointers will not cross and undo their own swaps.
Pattern: Opposite-End Convergence
Recognition cues:
- The problem asks to 'reverse' a sequence.
- The problem demands an 'in-place' algorithm with O(1) extra memory.
- The problem requires validating symmetry (palindromes).
Failure signals
- You are calling `.reverse()` in a high-level language without understanding that it allocates O(N) memory under the hood.
- Your loop condition is `left <= right` when swapping, which causes the middle element to uselessly swap with itself.
Engineering examples
Embedded Systems
Processing raw serial port text in microcontrollers that lack a garbage collector.
In-place two-pointer manipulation prevents heap fragmentation by mutating the existing character buffers directly.
Data Pipeline Sanitization
Stripping whitespace from millions of log entries.
A fast/slow two-pointer approach overwrites spaces in a single pass without copying strings.
When not to use
- Strings are strictly immutable in your language: In Java or Python, you cannot mutate strings in-place. You MUST convert them to a character array first (costing O(N) space), perform the two-pointer logic, and join them back. The two-pointer logic is still faster than naive copying, but true O(1) space is impossible without mutable buffers.
Common mistakes
- Out of bounds errors: Always ensure the `left` pointer never exceeds the array length and the `right` pointer never drops below 0, especially when adding inner `while` loops to skip characters.
- Skipping characters incorrectly: If moving `left` forward to skip spaces, you must STILL ensure `left < right` inside that inner loop, otherwise `left` will blast past the end of the array.
Glossary
- converge
- Moving closer together from opposite sides until meeting in the middle.
- conditional logic
- Rules in a program that decide what to do next based on specific tests (like 'if X, then Y').
- paradigm
- A typical pattern, model, or fundamental way of solving a certain type of problem.
Recall questions
- What is the primary spatial advantage of the two-pointer reversal technique?
- What loop condition prevents the pointers from crossing and undoing their work?
- What is the structural invariant regarding the characters outside the pointers?
Questions & answers
Reverse only the vowels of a given string.
Use two converging pointers. Move `left` until it hits a vowel. Move `right` until it hits a vowel. Swap them, increment/decrement, and continue until they cross.
Approach: Conditional two-pointer convergence.
Given a string containing only letters, reverse it without affecting the positions of special characters.
Use two pointers, `left` and `right`. If either points to a non-letter, advance it. Otherwise, swap and advance both.
Approach: Two pointers with conditional skipping.
Interesting facts
- The C standard library function `strrev()` is historically implemented using exactly this two-pointer logic.
Continue learning
Previous: String Traversal
Next: Palindromes
Related: Palindromes