In-Place Operations(JavaScript Array Edition)

As I prepare for technical interviews, this week I continued to explore the popular two-pointer technique to perform in-place operations.

Why are in-place algorithms so popular? Because they can help us save time and space.

Take the following method for example, this in-place algorithm avoids the cost of initializing or having to copy the array onto a new array with squared values, or of having to allocate added space in which to store the new squared values. With an in-place solution, instead we can simply square AND reassign each element while iterating through the array.

function squareInPlace(arr) {

  arr.forEach((int, index) => {
    arr[index] *= int;
  });

  // NOTE: no need to return anything - we modified arr in place
}

With this in mind, provided the following example found on Interview Cake how do we go about reversing a list of words in place?

Q: You’re working on a secret team solving coded transmissions.

Your team is scrambling to decipher a recent message, worried it’s a plot to break into a major European National Cake Vault. The message has been mostly deciphered, but all the words are backward! Your colleagues have handed off the last step to you.

Write a function reverseWords() that takes a message as an array of [strings] and reverses the order of the words in place.

let arr = ["!", "cake", "that", "me", "give"];
function reverseWords(arr) {
  let counter = 0;
  for (let i = arr.length - 1; i >= counter; i--) {
    let tempVar = arr[i]; 
    arr[i] = arr[counter];
    arr[counter] = tempVar;
counter++;
  }
  return arr;
}
function reverseWords(arr) --> ["give", "me", "that", "cake", "!"]

Using the two-pointer system, one pointer helps us keep track of the values to be swapped while the other pointer tracks the values these will be swapped with. Let’s break this down:

I began my iteration at the end of the array, however, you can certainly begin iterating at the front. First I defined a variable labeled counter which I set to zero; counter will mark the index of the element replacing the corresponding i value. Next I defined my for loop. The for loop will continue to run while i >= counter. After each iteration i decreases by 1 and count increases by 1, meeting at the midpoint index[2] or “that”, where my for loop ends.

Lets look at what is happening inside of the loop:

• First I declare a temporary local variable to help keep track of the values I am swapping i with
• I then swap arr[i] with arr[counter]
• Next I swap arr[counter] with the temporary variable previously declared
• Finally, I increase my counter variable by 1 for each new loop run-through

Once I am done iterating through my for loop I return arr, remember this problem calls for an in-place or destructive solution which means we can simply return the altered array.

The above solution results in the ideal O(1) extra space and O(n) time. Such operations are therefore preferred to nondestructive or out-of-place algorithms.

A similar example (LeetCode) for which the two-pointer technique helps us arrive at an in-place solution:

Q: Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Input: nums = [3,2,2,3], val = 3
function removeElement(nums, val) {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      let temp = nums[count];
      nums[count] = nums[i];
      nums[i] = temp;
      count++;
    }
  }
  return count;
}
Output: 2, nums = [2,2]

Just as in the previous example, herein I used the two-pointer system to come up with an in-place solution. Although the wording differs, the task is the same. We need to a) iterate through an array to find something that either meets a condition or does not and then we need to b) within the same array, separate or create some sort of divide between the elements in order to be able to select just what is needed.

For problems like these the two-pointer technique can provide a fast and efficient in-place solution. Consider using it!

Thank you for reading!