LeetCode · #344
Reverse String Solution
Write a function that reverses a string. The input is given as an array of characters s. Do it in-place with O(1) extra memory.
01
Section One · Problem
Problem Statement
Write a function that reverses a string in-place. The input is given as a character array s. You must do this by modifying the input array directly with O(1) extra memory.
Example 1
Input: s = ["h", "e", "l", "l", "o"]
Output: ["o", "l", "l", "e", "h"]
Example 2
Input: s = ["H", "a", "n", "n", "a", "h"]
Output: ["h", "a", "n", "n", "a", "H"]
Constraints
• 1 ≤ s.length ≤ 10⁵ • s[i] is a printable ASCII character • Must use O(1) extra memory
02
Section Two · Approach 1
Brute Force — New Array O(n)
Create a new array, copy elements in reverse order, then copy back. Or use a stack: push all characters, then pop them back. Both use O(n) extra space.
Why we can do better
Problem: Both approaches allocate O(n) extra memory. Reversing in-place only requires swapping elements from opposite ends — no extra storage beyond a single temporary variable.
Java — Stack-based (O(n) space)
import java.util.Stack;
class Solution {
public void reverseString(char[] s) {
Stack<Character> stack = new Stack<>();
for (char c : s) stack.push(c);
for (int i = 0; i < s.length; i++)
s[i] = stack.pop();
}
}
Python — Slice (O(n) space)
class Solution:
def reverseString(self, s: list[str]) -> None:
s[:] = s[::-1] # creates a reversed copy internally
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) — violates O(1) constraint |
03
Section Three · Approach 2
Two Pointers — O(n) time, O(1) space
Place one pointer at position 0 and one at position n−1. Swap the characters at both pointers, then move them inward. Repeat until they meet in the middle.
💡 Mental model: Two people stand at opposite ends of a row of cards. They simultaneously pick up their cards, swap them, step inward, and repeat. After n/2 swaps, the entire row is reversed.
Algorithm
- Step 1: Set
left = 0,right = n - 1. - Step 2: While
left < right: swaps[left]ands[right]. - Step 3:
left++,right--. - Step 4: When pointers cross → done. Array is reversed.
🎯 When to recognize this pattern:
- Any in-place transformation that pairs the first element with the last, second with second-to-last, etc. — use converging two pointers.
- This is the simplest and most fundamental two-pointer pattern.
- It appears in reversals, palindrome checks, and partitioning problems.
04
Section Four · Trace
Visual Walkthrough
Trace through s = ['h', 'e', 'l', 'l', 'o']:
Two Pointers — swap from both ends
Notice:
- Only ⌊n/2⌋ = 2 swaps needed for a 5-element array. The middle element stays in place.
- For even-length arrays, all elements get swapped.
05
Section Five · Implementation
Code — Java & Python
Java — Two Pointers
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
Python — Two Pointers
class Solution:
def reverseString(self, s: list[str]) -> None:
left, right = 0, len(s) - 1 while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Stack / New Array | O(n) | O(n) | Violates O(1) space constraint |
| Two Pointers ← optimal | O(n) | O(1) | n/2 swaps, one temp variable |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Single character | ['a'] | left == right immediately — no swaps, array unchanged. |
| Two characters | ['a', 'b'] | One swap → ['b', 'a']. Minimum case that actually reverses. |
| Palindrome | ['a', 'b', 'a'] | Reversal produces the same array. Swaps still execute, just swap same values. |
| Even length | ['a', 'b', 'c', 'd'] | n/2 = 2 swaps. No middle element left alone. |
| Odd length | ['a', 'b', 'c'] | Middle element 'b' stays. Pointers cross there. |
⚠ Common Mistake: Using
left <= right instead of left < right. When left equals right, swapping an element with itself is harmless but unnecessary. The correct condition is left < right — stop when pointers meet or cross.