Reverse String
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.
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, which points to working from both ends toward the middle.
Key Constraints:
1 <= s.length <= 10^5→ With n up to 100,000, the solution must run in O(n) time. Combined with the O(1) space requirement, this points to an in-place two-pointer swap.O(1) extra memory→ Constant space, so no reversed copy is allowed. A recursive solution uses O(n) stack space, which violates this in the strict sense.s[i]is a printable ASCII character → Single-character data with no multi-byte or encoding concerns.
Approach 1: Brute Force (Extra Array)
Intuition
Create a new array, fill it with the characters in reverse order, then copy everything back into the original array. The logic stays simple: read from the end of the input and write to the beginning of the copy.
This violates the O(1) space constraint, but it sets up what "reversing" means before we remove the extra array.
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 works but uses extra space, violating the constraint. Since each character has exactly one destination, its mirror position, we can swap each pair in the original array directly and skip the copy.
Approach 2: Two Pointers (Optimal)
Intuition
Reversing an array is a series of swaps between mirror positions. Position 0 swaps with position n-1, position 1 swaps with position n-2, and so on. This needs no extra space, only two pointers moving toward each other from opposite ends.
The character at position i belongs at position n - 1 - i, and the character at n - 1 - i belongs at i. A single swap places both into their final positions, so each pair is touched once and never revisited. That gives floor(n/2) swaps total.
The condition left < right covers both parities. For an odd length, the middle element is already at its mirror position, so the loop stops at it without a swap. For an even length, the pointers cross after the final swap. Either way the loop ends with every position correct.
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 optimal in both time and space. The same swap-the-ends logic can also be written recursively, which does not improve performance but expresses the problem as a smaller version of itself.
Approach 3: Recursion
Intuition
Reversal is self-similar. Swap the first and last characters, and the remaining work is "reverse everything in between," which is the same problem on a smaller array. This continues until the range holds one character or none, where there is nothing to swap.
This does not improve on the two-pointer solution. It is worse, because the call stack adds O(n) space for what the iterative version does in O(1).
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.