Remove Duplicates from Sorted Array
One of LeetCode’s easy challenges the following problem description; ‘Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.’
This problem is made easier by the fact that the array is sorted at the same time challenging by the constraint of replacing must be done in-place, this means we cannot create a new array and copy over items to it.
In order to follow a good approach to this problem, think of an array as a form of a linked list. Each element follows the other in a chain, this will help us visualize an important property we use in linked list, the head of the linked list.
Our approach will involve of keeping track of two indices (pointers). I will refer to this pointers as head and cursor. The head index, points to the last non-duplicate element in our list. The cursor index, points to our current element in our loop.
As mentioned, this approach involves looping through the elements in our array. On each iteration, we will check if the current element (at cursor index) is equal (duplicate) to the element at head index. If the element is a duplicate, we will continue the loop, effectively moving the cursor index. If the element is not a duplicate, we will move the head index one position forward and replace this element with the non-duplicate element at our cursor index.
Let’s step through this using a few illustrations to paint a clearer picture.
Our initial array and setup looks as follow. We can setup our cursor inside our loop as the next element, this is because the first element is definitely equal to itself.
int num [] = {0,0,1,1,2,3,4};int headIndex = 0;for (int cursorIndex = headIndex + 1; cursorIndex < nums.length; cursorIndex++)
{}
Since the second element is equal to the first element, we keep the head index and the cursor index is incremented by the loop.
On our next iteration the element at the head element is not equal to the element at the cursor index. In order, to update our array we need to update the element at the second position in our array. Therefore, we move our head index one position forward and replace the element at the incremented head index position with the element at our cursor index.
The same process continues, as follow below.
In our final iteration, our head index will be at the position of our lat non-duplicate element. Since the head index is an index, we need to factor in zero-based index in arrays. Therefore, to get the length of our array of our non-duplicates we increment the index by one.
Since arrays, have a fixed length it makes it difficult to remove the remaining elements, our approach passes the test and we have all non-duplicate elements, kinda. On approach to remove all duplicates would be setting an arbitrary value to all elements after the head index.
In the case below you could replace with a negative number.
int arbitrary = 0;
for(int index = headIndex + 1; index < nums.length; index++) {
nums[index] = --arbitrary;
}The final implementation in Java winds up as below. Moreover, the code without setting arbitrary values suffices.
Happy coding!
