In-Place Array Operations — LeetCode Problems

I decided to base this week’s post on the following LeetCode exercises (both of which involve in-place operations performed on an array):

Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns 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 instructions require that we modify the array in-place therefore we cannot simply loop through the array pushing all of the non-duplicate numbers into a new array, for example.

Instead, we need to find a way of keeping track of the non-repeating elements, storing these in the front of the array, whilst looping through the rest of the array. How do we accomplish this? With pointers!

let nums = [0, 0, 1, 3, 3, 3, 4, 5, 7];
function removeDuplicates(nums) {
  if (nums.length === 0) {
    return 0;
  }
  let p1 = 0; //pointer 1 
  for (let p2 = 1; p2 < nums.length; p2++) { //pointer 2
    if (nums[p1] !== nums[p2]) {
      p1++;
      nums[p1] = nums[p2];
    }
  }
  return p1 + 1;
}
removeDuplicates(nums)-- > [0, 1, 3, 4, 5, 7,...];

In the solution above, I first check to see if the length of my array is zero — is it an empty array? Yes? I immediately return zero. If the array is not empty then I continue and define a variable “p1”. p1 acts as my first pointer. Following, I set up a for loop which I will use to iterate through the nums array. I start my second pointer “p2” at index 1. As I loop thru the array I will compare each element at p2 to the nums value at pointer 1 (nums[p1]). If my values match, I continue to increase pointer 2 until I find the next non-matching or equivalent element to then replace with p++. If adjacent elements DO NOT match, meaning there are no duplicates in sight, I continue to iterate thru the array normally by first increasing p1, then replacing this value with p2, this way I can now increase p2 and then p1, respectively. Lastly, after iterating through my entire for loop I return the value of p2 + 1. p2 being the index of the last non repeating element. We add 1 in order to obtain the length of non repeating elements.

MOVE ZEROS

Problem no. 2 requires us to, given an array nums, write a function to move all 0's to the end of the array while maintaining the relative order of the non-zero elements.

Rules:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Similar to the previous problem, herein we can also use the two-pointer approach to help us solve this problem. Whilst one pointer focuses on iterating thru the array the other keeps track of the non-zero numbers.

var moveZeroes = function (nums) {
  let p1 = 0;
  for (let p2 = 1; p2 < nums.length; p2++) {
    if (nums[p1] !== 0) {
      p1++;
      continue; //continue loop 
    }
    if (nums[p2] !== 0) {
      nums[p1] = nums[p2];
      nums[p2] = 0;
      p1++;
    }
  }
  return nums;
};

Above I start by declaring a variable “p1” which refers to my first pointer and is initially set to 0. p1 will point to zero values, i.e., the values I want replace. Next, I set up a for loop used to iterate through the nums array. Inside of my for loop I first check to see if the nums value at pointer 1 is 0. If it is, we move on to the second conditional statement which checks to see if the nums value at pointer p2 is zero, if it is we want to continue our loop moving on to the following p2 value as there is no point in replacing zero with zero.

Let’s say nums[p1] is not equal to zero, we do not want to replace a non-zero number with zero therefore we continue by increasing both p1 and p2, respectively.

And if p1 is zero but p2 is not? Well then we do what we initially set out to do, swap p1 (our zero value) with p2 (our non-zero value), and increment p1 before continuing our loop!

As you may have noticed in-place operations are a bit trickier to implement, yet given their preferred run-time and popularity in technical interviews they're important to master.

Thank you for reading!