Photo by Mr Cup / Fabien Barral on Unsplash

How to Remove Duplicates From a Sorted Array

When you’re doing technical interviews, some questions can be tricky. So, it’s important to make sure you understand the directions clearly. One such example is the common algorithm question for removing duplicates from a sorted array. You may be asked something like this:

Write a function called removeDuplicates that, given a sorted array nums, removes the duplicates in place—each element should only appear once. Return the new length of nums.

Do not create a new array. Only modify the input array in place with O(1) extra memory.

The directions may cause confusion because it seems like you’re being asked to remove elements from the array nums. My first instinct was to recall the array methods I could use to remove elements. There’s .pop(), but that can only be used to remove the last element from an array, so that won’t work. There’s also .filter(), but that would create a new array, and the directions specify not to.

The Solution

Another possibility that would not create a new array is reordering the elements. To do so, we would need some type of comparison system to identify two adjacent identical elements. We can achieve that by using two pointers. See below:

const removeDuplicates = nums => {
  let p1 = 0
  for(let p2 = 1; p2 < nums.length; p2++){
  }
}

In my function removeDuplicates, I accept a sorted array nums and then create a variable for the first pointer: p1. It will sit at the first index in nums. Then, inside a for loop, I create a second variable p2, which will keep track of the element following p1.

Now we can think about the logic inside the for loop. We need to create some kind of comparison system that decides what should happen if p1 is not equal to p2.

const removeDuplicates = nums => {
  let p1 = 0
  for(let p2 = 1; p2 < nums.length; p2++){
    if(nums[p1] !== nums[p2]){
      p1++
      nums[p1] = nums[p2]
    }
   }
}

First off, if the two elements are the same, p2 will advance one position forward per the conditions of the for loop. If the two elements are not the same, p1 will move forward one spot and replace that value with p2's.

p1  p2
[1, 1, 2, 3, 4, 4]  elements are the same
p1     p2
[1, 1, 2, 3, 4, 4]  p2 advances
    p1 p2
[1, 2, 2, 3, 4, 4]  p1 moves up and replaces its value with p2's

So on and so forth until we’re left with:

          p1   p2
[1, 2, 3, 4, 4, 4]

At this point, p2 has reached the end of the array. The goal was to return the length of the unique values in the array, so if we select p1, it’s at index 3. However, we need to add 1, since we start counting at index 0. We should also create a condition to return 0 if the nums array is initially empty. Altogether, we would have:

The return value would be 4. We’re all done!