How Would You Reverse an Array In Place?

#array #algorithms #javascript

Let's say you were given an array of characters, such as ['a', 'b', 'c', 'd', 'e']. How would you reverse this array in place (that is, have a space complexity of O(1))?

One solution to this problem involves having two pointers, which start at both ends of the array. Then, swap the elements at those points in the array. Once both elements have been swapped, move both pointers toward the middle, and keep doing this until the left pointer is no longer smaller than the right pointer.

To start, set two variables for the two pointers--

function reverseArray(arr) {
  let leftPointer = 0
  let rightPointer = arr.length - 1

  //...
}

Then, initiate a while loop to keep going as long as leftPointer is less than rightPointer. When I initiate while loops, I like to immediately include an increment or decrement--this helps me avoid accidentally creating an infinite loop.

function reverseArray(arr) {
  let leftPointer = 0
  let rightPointer = arr.length - 1

  while (leftPointer < rightPointer) {
    //...
    leftPointer ++
    rightPointer --
  }
}

This is the tricky part of the problem: swapping the elements. One solution to this involves temporarily storing one of the elements in a variable. Then, set one element to the other, and set the other to the temporary.

function reverseArray(arr) {
  let leftPointer = 0
  let rightPointer = arr.length - 1

  while (leftPointer < rightPointer) {
    let temporary = arr[leftPointer]
    arr[leftPointer] = arr[rightPointer]
    arr[rightPointer] = temporary

    leftPointer ++
    rightPointer --
  }
}

And that's it! If you tested this out with the array ['a', 'b', 'c', 'd', 'e'], the function would return ['e', 'd', 'c', 'b', 'a']. The time complexity for this solution would be linear, O(n).