344. Reverse String
https://leetcode.com/problems/reverse-string/
Feel free to give this a go and send me your solution.
Problem
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.
Solution
Approach
First we need to read carefully and understand the problem. Don’t skip this step and immediately start coding up a random solution, it’ll only come back to bite you later!
When I read this I can see three main points:
we have some input in the form of an array of characters called s.
the output should be the reverse of the input
we have a constraint on the problem, it must modify the input array in-place.
The first two points are pretty simple and shouldn’t need too much explanation but the third point is very important. We cannot create another array to solve this problem and have to use the existing array that already contains the array of characters.
My Attempts
The simplest solution I can think of to this doesn’t satisfy the third of our criteria and therefore would fail as a solution for this problem on the LeetCode website. That doesn’t mean its not a valuable stepping stone to the solution though!
This is to create a new array and loop through the input backwards, lets see some pseudocode:
function(input):
create new array[with_size_of_input]
loop each character backwards through input:
array.add(character)
return array
This should create the desired output and it would definitely reverse a string.. but it will also use too much memory. We have created a new array in memory on our computer.
What if we were to use a temporary variable to swap the first and last character of the array? Then the second with the second-to-last and so on until we hit the middle.
I’m going to propose a two pointer algorithm as a solution to this problem. We can create two small variables to point at the first and last character of the array and then on each iteration swap the characters and move them closer together until they converge!
Lets try to visualise it:
[1, 2, 3, 4, 5, 6]
^ ^
[6, 2, 3, 4, 5, 1]
^ ^
[6, 5, 3, 4, 2, 1]
^ ^
[6, 5, 4, 3, 2, 1]
My solution in C#:
public void ReverseString(char[] s) {
int left = 0;
int right = s.Length - 1;
char temp;
while(left < right) {
temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
I’ve intialised a left and right variable as pointers to use in the input array. This way we can traverse the array by changing the pointer value. The left one starts at the first element in the array and the right one starts at the last element.
The while loop checks if the pointers have met in the middle yet and if not will continue on the next loop.
we use a temp variable to store the current value where the left is looking at, then we overwrite that left value with the right value then we assign the temp value to the right side. We have swapped the elements.
Finally we increment left and decrement right, slowly moving them closer together.
Once they converge we have a reversed array of characters!
Complexity
Time complexity of this solution is O(n) because the while loop iterations are O(1) each, and the pointers start at a distance of n from each other and move closer by one step each iteration. This can never cause us to do more than n iterations.
Space complexity of this solution is O(1) we don’t use any more memory to complete this solution we don’t initialise new arrays to complete any calculations.
We do, however, use two small variables as pointers on my machine in C# this is 4 bytes each for 8 bytes total in integers and 2 bytes for the char totalling 10 bytes. Much, much smaller than the potential size of a copy of the unspecified input array.