344. Reverse String - Detailed Explanation
Problem Statement
Given an array of characters, reverse the array in-place. The function should modify the input array directly without using extra space for another array.
Example 1
- Input: s = ['h', 'e', 'l', 'l', 'o']
- Output: ['o', 'l', 'l', 'e', 'h']
- Explanation:
After reversing, the first character becomes 'o', the second 'l', and so on.
Example 2
- Input: s = ['H', 'a', 'n', 'n', 'a', 'h']
- Output: ['h', 'a', 'n', 'n', 'a', 'H']
- Explanation:
The reversed array reads the same as the original when considering the order of characters, even though the cases of the first and last letters are swapped.
Constraints
- 1 <= s.length <= 10⁵
- s[i] is a printable ASCII character.
- The reversal must be done in-place, using O(1) extra space.
Hints
-
Two-Pointer Technique:
Think about maintaining two pointers—one at the beginning and one at the end of the array. By swapping the characters at these pointers and moving them towards the center, you can reverse the array in-place. -
Edge Cases:
Consider what happens when the array has only one character or is empty. How should the pointers behave in those cases?
Approach 1: Using Extra Space (Not In-Place)
Explanation
A simple solution involves creating a new array that stores the characters of the original array in reverse order. Although this approach is straightforward, it does not satisfy the in-place requirement because it uses O(n) extra space.
Step-by-Step Walkthrough
-
Create an empty array (or list) to hold the reversed characters.
-
Iterate over the input array from the last character to the first.
-
Append each character to the new array.
-
Optionally, copy the new array back into the original array.
Complexity Analysis
-
Time Complexity: O(n), where n is the length of the array.
-
Space Complexity: O(n) due to the additional array.
Python Code (Using Extra Space)
Java Code (Using Extra Space)
Approach 2: Two-Pointer Technique (Optimal In-Place)
Explanation
The optimal solution reverses the array in-place using two pointers:
- Left Pointer: Starts at the beginning of the array.
- Right Pointer: Starts at the end of the array.
By swapping the characters at these pointers and then moving the left pointer one step to the right and the right pointer one step to the left, the array is reversed without using extra space.
Step-by-Step Walkthrough
-
Initialize Pointers:
Setleft = 0andright = len(s) - 1. -
Swap Characters:
Whileleft < right, swaps[left]ands[right]. -
Move Pointers:
Incrementleftby 1 and decrementrightby 1. -
Stop Condition:
Continue untilleftis no longer less thanright.
Visual Example
Consider the array:
s = ['h', 'e', 'l', 'l', 'o']
-
Iteration 1:
left = 0('h'),right = 4('o')- Swap → s becomes ['o', 'e', 'l', 'l', 'h']
- Update pointers:
left = 1,right = 3
-
Iteration 2:
left = 1('e'),right = 3('l')- Swap → s becomes ['o', 'l', 'l', 'e', 'h']
- Update pointers:
left = 2,right = 2
-
Iteration 3:
- Now
left == right(both point to the middle character 'l'), so stop.
- Now
Complexity Analysis
- Time Complexity: O(n), where n is the number of characters.
- Space Complexity: O(1), since no additional storage is used.
Python Code (Optimal In-Place)
Java Code (Optimal In-Place)
Common Mistakes and Edge Cases
-
Not Swapping Correctly:
Be careful with index arithmetic. Swapping the wrong indices can lead to incorrect results. -
Off-By-One Errors:
Ensure that the while loop stops whenleftis equal toright. Overstepping can cause unnecessary swaps or index errors. -
Edge Cases:
- Empty Array: The function should handle an empty array gracefully.
- Single Character: No swap is needed when there is only one character.
Alternative Variations
-
Reverse Words in a String:
Instead of reversing the characters in an array, you might be asked to reverse the order of words in a sentence. -
Recursive Approach:
You can also reverse the string recursively. However, this approach uses the call stack and may not be as efficient as the two-pointer technique for very large arrays.
Related Problems
GET YOUR FREE
Coding Questions Catalog
