Reverse String
Reverse String: reverse an array of characters in place, using O(1) extra memory rather than allocating a second array.
- 1 <= s.length <= 10⁵
- s[i] is a printable ASCII character
- Modify the input array in place with O(1) extra memory
Intuition
Reversal is a set of swaps, not a rebuild. The character at position i must end up at position n - 1 - i, so pairing the first with the last, the second with the second-last, and so on performs the whole reversal with no new storage. Two pointers walking toward each other enumerate exactly those pairs, and they meet after n / 2 swaps because each swap settles two positions at once.
Converging two pointers is the tool whenever a problem pairs the front of a sequence with the back — reversal, palindrome checks, or two-sum on a sorted array. The signal is a relationship between index i and index n - 1 - i.
Approach
Before reading on: work out which index each position must swap with, and convince yourself why the loop must stop when the pointers meet rather than when they cross. Try it on a 5-character array and count the swaps.
Pair each index with its mirror
In a reversed array of length n, the element originally at index i lands at index n - 1 - i. That mapping is its own inverse: applying it twice returns the original index. So the array decomposes into disjoint pairs (i, n - 1 - i), and swapping the two members of every pair completes the reversal. Because the pairs are disjoint, order does not matter and no element is moved twice — which is precisely what makes a single linear pass sufficient.
Two pointers converging, and where they stop
Set left = 0 and right = n - 1 and swap while left < right, advancing left and retreating right after each swap. The condition is strict for a reason. When n is odd the pointers eventually land on the same index, and that middle character is already in its final position — it is its own mirror. Swapping it with itself is harmless but pointless; continuing past that point would begin undoing the swaps already made, reversing the array back to its original order.
Why in-place matters here
Building a reversed copy is trivial in every language, but the problem forbids it, and the constraint is the lesson. In-place work keeps memory at O(1) regardless of input size, which is what lets the same routine run on a buffer too large to duplicate. The swap itself needs no temporary in Python, where tuple assignment evaluates the right-hand side first; C++ and Java use std::swap or an explicit temp variable. Time is O(n) with n/2 swaps, space O(1).
Solution & live demo
Common pitfalls
Looping while left <= right
while left <= right:
s[left], s[right] = s[right], s[left]while left < right:
s[left], s[right] = s[right], s[left]On odd lengths the pointers land on the same index and swap the middle element with itself — harmless — but the real risk is the same condition used with pointers that keep moving past each other, which re-swaps every pair and restores the original order.
Building a new list instead of mutating
s = s[::-1]
s[:] = s[::-1]
Rebinding the local name s leaves the caller's array untouched, so the function appears to do nothing. The problem requires the input itself to change, which needs slice assignment or explicit swaps.
Advancing only one pointer
while left < right:
s[left], s[right] = s[right], s[left]
left += 1while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1With right frozen, left walks all the way to the end and every element is repeatedly swapped with the last one, scrambling the array instead of reversing it.
Edge cases
left starts at 0 and right at -1, so the loop never runs.
left == right immediately; the strict condition skips the pointless self-swap.
Exactly 2 swaps, and the pointers cross without ever meeting.
2 swaps; the middle character is its own mirror and stays put.
The swaps still run but the visible result is unchanged.