Click here to see the problem. And read the description and try to understand the problem first.
Reverse String is one of the most common problems in computer programming. And this time, the input string is given as an array of characters. We have to return the reverse version of the given array. See the example from the problem’s description.
Input: ['h', 'e', 'l', 'l', 'o']
Output: ['o', 'l', 'l', 'e', 'h']In general, we can solve this problem by traversing from the end of the array and storing the result in a new array. After the loop, we’ll get our desired result. Which is something like that:
def reverseStr(arr):
new_arr = []
i = len(arr) - 1
while i >= 0:
new_arr.append(arr[i])
i -= 1
return new_arr
lst = ['h', 'e', 'l', 'l', 'o']
print(reverseStr(lst)) # Output = ['o', 'l', 'l', 'e', 'h']The time and Space complexity of this solution is O(n). It takes O(n) space just because we take a new array for storing elements where n is the size of the array. But the problem’s description clearly says that we are not allowed to allocate any extra memory for a new array.
So, how can we do this by modifying the input array in-place with O(1) extra memory?
To solve this problem, we’ll use two pointer technique. Where one will point to the first element, and another will point to the last element of the given array. In each iteration, one will move forward (start), and another will move backward (end). Every time we will swap values between two positions. We’ll continue this until the two-pointer meet each other. Using this technique, we can solve this problem in O(1) space.
We don’t need to return anything. Let’s see the solution in Python.
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
start = 0
end = len(s)-1
while start < end:
s[start], s[end] = s[end], s[start]
start += 1 # move one-step forward
end -= 1 # move one-step backwardI hope this will help you to understand this problem. If it does, it’s a pleasure for me.
Happy Learning 🙂
Happy Coding 🙂
