Removing Duplicates from a Sorted Array

For any given Leetcode problem you can typically find an abundance of online solutions. Some are good, some are bad, some will work out of the box but too many are just flat wrong.

I found this to be true with Google’s top 10 search results for Leetcode’s problem #26 , “Remove duplicates from a sorted array”. Given that my findings we’re slim and misleading, I’ve decided to just post and explain my solution here.

Heres the line by line breakdown:

Line 17: start out at index 1. Index 0 is irrelevant sense we are comparing index 1 against 0 to check for uniqueness.

Line 18: For loops in some languages handle updates in values used to determine if it should continue looping while some don’t. When needing to have more control over a loop like in our case where we’re change i conditionally, its better to use a while loop.

Line 19: Our only edge-case. If we’ve hit the point in our array where all that is left is underscores, we’ve completed our duplicate removal and can return.

Line 23: The most important conditional in this problem. If the previous index holds the same value as the current index, delete the value at the current index. Sense our array is arranged in ascending order, we can alwasy expect the previous value to either be a duplicate or not be a duplicate.

Line 25–26: If the previous value is not the same, there is no further duplicates associated with this index and we can increment our counter for the next index.

Line 8: given the index we wish to delete, the array reference and the arrays fixed length.

Line 9: Set the value for the index we deemed a duplicate to an underscore.

Line 10–14: starting with the index whose value we just changed to and underscore, swap it with the next value until it is at the end of the array. You can improve the time complexity of this further by checking if the next value is an underscore and if so, stop.

Using Javascript’s Splice

If you want to use javascript’s native index deletion method splice(), all you have to do is replace your call to deleteDupe() with splice(i, 1) .