DEV Community

loading...

How Would You Reverse an Array In Place?

Alisa Bajramovic
・1 min read

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

  //...
}
Enter fullscreen mode Exit fullscreen mode

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 --
  }
}
Enter fullscreen mode Exit fullscreen mode

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 --
  }
}
Enter fullscreen mode Exit fullscreen mode

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).

Discussion (1)

Collapse
ionellupu profile image
Ionel lupu

This can be done with only the leftPointer. The rightPointer can be deduced from arr.length - leftPointer - 1.

Also, isn't Array.prototype.reverse() O(n)? It looks like, as per spec, they do almost the same thing: