Reverse String - Solution & Explanation
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.
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.
Approach Overview
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 1: Two-Pointer Approach
The two-pointer technique involves using two pointers, one starting at the beginning of the array and the other at the end. Swap the characters at the two pointers and then move the pointers inwards towards each other until they meet or cross. This method efficiently reverses the array in-place with O(1) extra space.
The C solution uses a while loop with two pointers, left and right, to swap the characters until the entire string is reversed. The process continues until the left pointer is not less than the right pointer.
Complexity
Time Complexity: O(n) where n is the number of characters in the string.
Space Complexity: O(1) as it uses a fixed amount of extra space.
Approach 2: Recursive Approach
This approach uses recursion to swap characters at symmetric positions while visually simplifying the problem. The base case is when the left index is not less than the right index.
Recursive function in C swaps characters starting from outermost towards the middle, reducing the problem size in each call.
Complexity
Time Complexity: O(n).
Space Complexity: O(n) due to call stack depth.
Approach 3: Two Pointers
We use two pointers i and j, initially pointing to the start and end of the array respectively. Each time, we swap the elements at i and j, then move i forward and j backward, until i and j meet.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n) where n is the number of characters in the string. |
| Recursive Approach | Time Complexity: O(n). |
| Two Pointers | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Reverse String - 3 Ways - Leetcode 344 - Python • NeetCode • 89,819 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse String easy or hard?
How to solve Reverse String in O(n)?
Reverse String Python or Java solution?
What is the best approach for Reverse String?
What data structure is used in Reverse String?
What is the time complexity of Reverse String?
Is Reverse String asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Reverse String with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor