Watch 10 video solutions for Reverse String, a easy level problem involving Two Pointers, String. This walkthrough by Greg Hogg has 328,465 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 <= 105s[i] is a printable ascii character.Problem Overview: You are given a character array s and must reverse it in-place. The function cannot allocate extra space for another array; the reversal must happen by modifying the original array directly.
Approach 1: Two-Pointer Approach (O(n) time, O(1) space)
This is the standard in-place solution. Use two indices: one starting at the beginning of the array (left) and one at the end (right). Swap the characters at these positions, then move left++ and right-- until the pointers meet in the middle. Each element is visited at most once, giving O(n) time complexity. Since the swaps happen directly inside the input array without extra storage, the space complexity remains O(1). This technique is a classic application of the Two Pointers pattern and works efficiently for problems where you process elements from both ends of a sequence.
The key insight is that reversing a sequence simply means exchanging symmetric elements around the center. For example, the first character swaps with the last, the second with the second-last, and so on. You only need to process half the array because each swap places two characters in their final position. This approach is optimal for array-based string manipulation problems where in-place updates are required.
Approach 2: Recursive Approach (O(n) time, O(n) space)
The recursive solution performs the same symmetric swaps but delegates the remaining work to recursive calls. Start with two indices (left and right). Swap s[left] and s[right], then recursively call the function with left + 1 and right - 1. The recursion stops when left >= right, meaning the middle of the array has been reached.
Each recursive call processes one pair of characters, so the total number of operations is still O(n). However, the recursion stack stores up to n/2 function calls, resulting in O(n) auxiliary space. While this approach is conceptually elegant and demonstrates understanding of recursion, it is less space-efficient than the iterative two-pointer method.
Recommended for interviews: The two-pointer approach is what interviewers expect. It demonstrates awareness of in-place array manipulation and optimal space usage. Mentioning the recursive version shows deeper algorithmic understanding, but the iterative two-pointer solution is the cleanest and most efficient implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Approach | O(n) | O(1) | Best general solution when the string/array must be reversed in-place with minimal memory. |
| Recursive Approach | O(n) | O(n) | Useful for demonstrating recursion concepts or practicing divide-and-conquer thinking. |