Remove Duplicates from Sorted Array

I’m going to walk through a JavaScript solution to the Remove Duplicates from Sorted Array question from LeetCode’s Top Interview Questions (Easy Collection).

Here’s the question exactly as it is on LeetCode:

So, we are given an array of sorted integers and need to return a count of how many integers are not repeated, meanwhile modifying the array to have all non-repeated integers in the front, in the same order. (Btw, “non-decreasing order” just means that the given integers never decrease in value, only either stay the same or increase.)

One of the hints in LeetCode suggests using a two-pointer approach with … “one that would keep track of the current element in the original array and another one for just the unique elements.”

This JavaScript solution has a runtime of 88ms (beats 80% of JS solutions) and memory usage of 41.4MB (beats 45% of JS solutions).

First we set variable j, which will keep track of the lower number, then we loop through the array with i, starting with the index after j, which is 1. When nums[i] does not equal nums[j] then we replace the integer just after the lowest number with the next higher integer.

Get K. Johnson’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Let’s now walk through an example with the input [1, 1, 1, 2, 2, 3, 5].

• j is set at 0, the loop starts with i at index 1
• the if statement compares nums[j] with nums[i] (1 with 1) and determines they are the same so the loop continues
• j is at index 0, i at index 2… integers 1 and 1 are the same so the loop continues
• j is at index 0, i at index 3… integers 1 and 2 are not the same so j is incremented by 1 to become 1. nums[j] is set to the value of nums[i] so the value at index 1 becomes the integer 2
• the nums array now looks like [1, 2, 1, 2, 2, 3, 5]
• the loop continues with j now at index 1 and i at index 3 and compares 2 with 2
• loop continues with j at index 1 and i at index 4 comparing 2 with 2
• loop continues with j at index 1 and i at index 5 comparing 2 with 3, j is then incremented to index 2 and the value at index 2 is replaced with the integer 3
• the nums array now looks like [1, 2, 3, 2, 2, 3, 5]
• loop continues with j at index 3 and i at index 6, comparing 3 with 5 and the value at index 3 is replaced with the integer 5. if the loop were to continue i would no longer be less than nums.length so the loop stops.
• the final nums array is now [1, 2, 3, 5, 3, 5]
• since j ended at the index of the last unique value we will return the length of unique values to j + 1 and return that amount (4).

Please feel free to comment! Contribution is absolutely welcomed. ty :)