LeetCode #26 Solved: Remove Duplicates

The key to solving problems on LeetCode is looking for patterns and keywords that give you a hint as to what you should do. One example of a question with a keyword that makes it easy to come up with a solution is LeetCode #26: Remove duplicates from a sorted array. Just to point out the "hint" that LeetCode gives in the question, here's what it says:

The keyword to notice here is in-place, which essentially refers to the in-place algorithm. If you don't know what it is, it's basically an algorithm that works directly on the given data structure and doesn't require any extra space proportional to the size of the input. As the term suggests, it changes the input in its place without making a copy of the data structure. You can read more about it here.

The question also lists what you need to do for your answer to be accepted:

So, the question has 2 parts:

1. Change the array and have all the unique elements appear in order in front of the array. The remaining duplicate elements aren't important.

2. We have to return the first unique k elements of the array. In other words, we can think of this as the index of the last unique element in the array.

Now that we have all the information, we can start solving this question. We first need some way to keep track of where the unique elements should be inserted. And that's simple to do:

let insertIndex = 0

Then, we need to iterate through the array and find duplicates. Since the array given to us is already sorted in ascending order, we can simply check for non-duplicates by checking two consecutive elements in the array:

 for(let i=0; i<nums.length;i++){
        if(nums[i]!==nums[i+1])

In the if condition, we're basically checking if an element (nums[i]) isn't equal to the element right after it (nums[i+1]). If it isn't equal, that means we have a unique element, and we can just assign nums[i] to the position indicated by the insertIndex in the array. Doing so overwrites the duplicates with unique elements and keeps all unique elements toward the start of the array. If this sounds confusing, don't worry; the visual example at the end will help. Once we overwrite the duplicate, we just need to increment our insertIndex so that we can use it to insert the next unique element and not rewrite the one we inserted last:

nums[insertIndex] = nums[i]
insertIndex++

Once the loop ends, we're going to be left with only unique elements at the beginning of the array. Now all that's left for us to do is return the number of unique elements, and, as mentioned above, this is just the index of the last element we inserted, i.e., insertIndex, so we can just return that:

 return insertIndex

Working through an example

Let's work our way through this example:

I've indicated the indices in green. As we traverse the array, we're going to check our condition: nums[i]!==nums[i+1]. Let's visualize the iterations in a table:

Since the condition is false, the if loop will not be executed and we'll move on to the next iteration.

The if loop will now be executed and the following will run. Remember, we initialized our insertIndex to 0 before we began the loop.

nums[insertIndex] = nums[i]
insertIndex++

This means that nums[0] = nums[1], which is 0. This doesn't change our array yet since this is the first unique element that's already present at the beginning, but you'll see how insertIndex helps in the following iterations. And since we increment insertIndex, it's now 1, which means it's ready for a new unique element. We can then continue with the loop:

Now that the condition is true, nums[insertIndex] = nums[i], that means nums[1]=1. Our nums array then becomes [0,1,1,1,1,2,2,3,3,4] and insertIndex becomes 2.

nums[insertIndex], i.e., nums[2] = 2, so our nums array is now [0,1,2,1,1,2,2,3,3,4] and insertIndex is now 3.

nums[insertIndex] or nums[3] is now 3, making our nums array [0,1,2,3,1,2,2,3,3,4]. The insertIndex is incremented again and is now 4.

In JavaScript comparing undefined with anything else (except undefined) with the strict inequality operator (!==) returns true, which means 4!==undefined is true, and the if loop is executed. As a result, our nums array now becomes [0,1,2,3,4,2,2,3,3,4] and insertIndex is 5.

We now have all the unique elements at the front of the array and we also know that insertIndex is equal to the total number of unique elements in the array, so we can just return that, and we're done with the question!

As always, you can find the whole solution on my GitHub or you can run it directly on OneCompiler.

---

Solving Leetcode problems is hard enough as it is, and add to that the difficulty of finding an in-depth solution that explains everything, and you find yourself stuck. Some videos are hard to follow, some don't explain the basics, while others leave you with more questions than answers. In this series, I break down Leetcode problems one at a time and walk you through a step-by-step solution. Have a question you can't understand? Send it to me, and I'll explain it in detail. And don't forget to subscribe to my newsletter to get my articles directly into your inbox!