Leetcode 26: Remove Duplicates from Sorted Array

In this exercise, we have a sorted array nums, and we want to update it so that there is no duplicate anymore in-place, and we return the new length of the array. Once again, we first solve the problem without considering the in-place part and at the end figure out how to make it in-place.

a. Basics of removing duplicates

At the core removing duplicates is a 2-steps process of detecting each duplicate and removing it. So if we have a data structure that allows removal of elements such as a List, we can simply do:

// Copy array to List
List<Integer> lst = new ArrayList<>();
for (int i =0;i<nums.length;i++) {
    lst.add(nums[i]);
}
// Removal algorithm
int prev = lst.get(0);
int i = 1;
while (i < lst.size()) {
    if (lst.get(i) == prev) {
        // remove element
        lst.remove(i);
    } else {
        // Update prev and i
        prev = lst.get(i);
        i++;
    }
}

b. Removing in an array

In the exercise we don’t really delete anything, we just generate an array without duplicates. [1,1,2,2,3,3] -> [1,2,3,x,y,z], with x,y,z values ignored.

So instead of a removing operation, we are actually just assigning: nums[0] = 1, nums[1]=2, nums[2]=3.

c. Removing in place

To remove elements in place, we only need a pointer to know where to assign the unique values, and another pointer to traverse the…