🟩 Reverse String (#344)
🔗 Problem Link
📋 Problem Statement
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
💡 Examples
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"]
🔑 Key Insights & Approach
Core Observation: To reverse in-place, we need to swap elements from the outside moving inward. The first element swaps with the last, second with second-to-last, and so on.
Why Two Pointers?
- In-place requirement: Can't create a new array (
O(1)space constraint) - Symmetry: Reversing is inherently symmetric—work from both ends
- Efficiency: Each element is touched once -
O(n)time
When to Stop?
- When
left >= right(pointers meet or cross) - For odd-length arrays: middle element stays in place
- For even-length arrays: all elements get swapped
Pattern Recognition: This is the classic "Two Pointers - Opposite Ends" pattern, used for reversing, palindrome checking, and container with most water. Key trait: pointers move toward each other from both ends
🐍 Solution: Python
Approach 1: Two Pointers
Time Complexity: O(n) | Space Complexity: O(1)
def reverse_string(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
Approach 2: Pythonic (Using Slice)
Time Complexity: O(n) | Space Complexity: O(1)
def reverseString(s: List[str]) -> None:
s[:] = s[::-1]
🔵 Solution: Golang
Approach 1: Two Pointers
Time Complexity: O(n) | Space Complexity: O(1)
func reverseString(s []byte) {
left, right := 0, len(s)-1
for left < right {
// Swap elements
s[left], s[right] = s[right], s[left]
left++
right--
}
}
Approach 2: Two Pointers with Manual Swap
Time Complexity: O(n) | Space Complexity: O(1)
func reverseString(s []byte) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}