Reversing a String in Place

Today's algorithm of the day is the Reverse String problem:

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters.

This kind of problem (and variations on it) pop up all the time, so knowing how to modify an array in place is a super useful skill.

Today, I'm going to be solving this problem with two pointers--one at each end of the array--and "swapping" the letters at those spots. I'll start by going over the approach I'll be taking, and then I'll code out the solution using JavaScript.

Approaching this Problem

The idea behind a two pointer solution is to have a pointer at each end of a word (or array), to swap the letters at those points, and to keep moving the two pointers toward the middle of the word. By the time the pointers meet in the middle, the word will be reversed.

To better explain this idea, I'll use an example. We'll start with the word "TANDEM", and two pointers. The left pointer is at start, the "T", and the right pointer is at the end, the "M".

Now, we'll want to swap these two letters: "T" will go in the "M" spot, and "M" will go in the "T" spot. After swapping, we get the string "MANDET".

Now we can move our pointers toward the center. The left pointer is now on the "A", and the right pointer is on the "E". We will swap these letters, putting the "A" where the "E" was, and the "E" where the "A" was. After swapping, we get "MENDAT".

Again we move the pointers toward the center. The left pointer is on "N", and the right pointer is on "D". We'll swap these letters, and we have "MEDNAT", which is "TANDEM" backwards.

We know to stop because we always want the left pointer to be to the left of the right pointer. In other words, we'll want the process to keep going until the pointers meet at the middle.

Coding the Solution

Now that we've walked through how this solution would work, we can move onto coding it. To start, we'll want to make the pointers, left and right. We'll set left equal to 0, so that it starts at the beginning, and we'll set right equal to the length of the string minus 1, so that it starts at the end of the string (remember that indexing starts at 0).

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  //...
}

We'll want to keep doing something until left and right meet at the middle, which means this is a good time to use a while loop. As long as left is less than right (aka to the left of right), we'll want to be swapping the letters.

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    //...
  }
}

To do the swapping, we'll need to create two variables, which will both temporarily store the values at each index. We need these temporary variables or else the swapping couldn't work. To see why, let's briefly look at the example of "CAT". If we wanted to reverse this string, and didn't use temporary variables, we'd do something like

//...
str[left] = str[right] // right now, str = "TAT"
str[right] = str[left] // again, str = "TAT"
//...

Without temporary variables, therefore, we wouldn't have a way of "remembering" which variable used to be at the index.

So, we'll create tempStart and tempEnd. tempStart will store the variable at the left index, and tempEnd will store the variable at the right index.

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    const tempStart = str[left];
    const tempEnd = str[right];
    //...
  }
}

Now that the values are stored in these temporary variables, we can go ahead and swap them. We'll set the value at the left pointer equal to tempEnd, and the value at the right pointer equal to tempStart. And finally, we'll move the pointers--left will increment, and right will decrement, so that they both go toward the center.

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    const tempStart = str[left];
    const tempEnd = str[right];
    str[left] = tempEnd;
    str[right] = tempStart;
    left++;
    right--;
  }
}

This two pointer iterative approach is done in constant space (O(1)) and linear time (O(n)).

As always, let me know in the comments if you have any questions or ideas!

Comments

[noc@dev]

@alisabaj , If we go with only one variable inside while, is there any problem.?

looks ok to me.

function reverseString(str) {
    let left = 0;
    let right = str.length - 1;
    while (left < right) {
      const temp = str[left];
      str[left] = str[right];
      str[right] = temp;
      left++;
      right--;
    }
  }

[Роман Барахвостов]

Another way:

const reverse = (arr) => {
  let left = 0
  let right = arr.length - 1

  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]]
    left++
    right--
  }

  return arr
}