Reverse String
Last Updated: March 29, 2026
Understanding the Problem
We're given an array of characters and need to reverse it in place. "In place" means we can't create a new array and copy the reversed characters into it. We need to rearrange the existing array using only O(1) extra memory.
The key observation is simple but important: reversing an array means the first element swaps with the last, the second swaps with the second-to-last, and so on. Each element has exactly one "partner" it needs to trade places with. This naturally suggests working from both ends toward the middle.
Key Constraints:
1 <= s.length <= 10^5→ With n up to 100,000, we need O(n) or better. Combined with the O(1) space requirement, the two-pointer swap approach fits perfectly.O(1) extra memory→ The problem explicitly requires constant space. No creating a reversed copy. A recursive approach uses O(n) stack space, which technically violates this.s[i]is a printable ASCII character → Simple character data, no special encoding considerations.
Approach 1: Brute Force (Extra Array)
Intuition
The most natural first thought: create a new array, fill it with the characters in reverse order, then copy everything back into the original array. This makes the logic dead simple since we just read from the end and write to the beginning.
Of course, this violates the O(1) space constraint. But it's a useful starting point to understand what "reversing" actually means before we optimize.
Algorithm
- Create a new array
reversedof the same size ass. - Iterate through
sfrom the end to the beginning, placing each character at the next position inreversed. - Copy all characters from
reversedback intos.
Example Walkthrough
Input:
After reading from end to front into reversed:
Finally, copy reversed back into s:
Code
- Time Complexity: O(n). Two passes through the array: one to build the reversed copy and one to copy it back. Both are O(n).
- Space Complexity: O(n). We allocate a new array of the same size as the input. This violates the O(1) space requirement.
This approach works correctly but uses extra space, violating the problem's constraint. Since each character has exactly one destination (its mirror position), what if we just swapped each pair directly?
Approach 2: Two Pointers (Optimal)
Intuition
Reversing an array is just a series of swaps between mirror positions. Position 0 swaps with position n-1, position 1 swaps with position n-2, and so on. We don't need any extra space for this, just two pointers walking toward each other from opposite ends.
The two-pointer approach works because reversing is symmetric. The character at position i needs to end up at position n - 1 - i, and vice versa. By working from both ends simultaneously, each swap puts two characters into their final positions at once. We only need n/2 swaps to reverse the entire array, and we never need to revisit any position.
The condition left < right handles both odd and even length arrays correctly. For odd-length arrays, the middle element is already in its correct position, so we naturally skip it when the pointers meet. For even-length arrays, the pointers cross each other after the last swap.
Algorithm
- Initialize
left = 0andright = s.length - 1. - While
left < right: - Swap
s[left]withs[right]. - Increment
left, decrementright. - When
left >= right, the array is fully reversed.
Example Walkthrough
Code
- Time Complexity: O(n). We perform exactly floor(n/2) swaps. Each swap is O(1), so the total is O(n).
- Space Complexity: O(1). Only a few variables (
left,right,temp). No additional data structures.
The two-pointer approach is already optimal in both time and space. But can we express the same logic recursively? This won't improve performance but demonstrates a different way of thinking.
Approach 3: Recursion
Intuition
The recursive approach sees reversal as a self-similar problem. If you swap the first and last characters, the subproblem is "reverse everything in between." That subproblem has the same structure, just on a smaller array. This continues until the subproblem is a single character (or empty), at which point there's nothing to reverse.
This approach doesn't improve on the two-pointer solution. It's actually worse because of the O(n) call stack overhead. But interviewers sometimes ask for it to test your comfort with recursion.
Algorithm
- Define a helper function that takes
leftandrightindices. - Base case: if
left >= right, return (nothing to swap). - Recursive case: swap
s[left]withs[right], then recurse onleft + 1andright - 1.
Example Walkthrough
Code
- Time Complexity: O(n). We make n/2 recursive calls, each doing O(1) work. Same total work as the iterative approach.
- Space Complexity: O(n). The recursion depth is n/2, so the call stack uses O(n) space. This is the key disadvantage compared to the iterative approach.