Problem Description

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Wrong Code

public int removeDuplicates(int[] nums) {
    int c = nums.length;
    for(int i = 0; i < nums.length-1; i++){
        if (nums[i] == nums[i+1])
            c--;
    }
    return c;
}

Error Information

Your input [1,1,2]
Output [1,1]
Expected [1,2]

Wrong Thinking

I ignored the requirement that requirement of removing the duplicates, and I worte this only to return the length of array without duplicates which means the array wasn’t changed actually.

How Did I Correct the Code

Review

The reason why i was wrong is not doing the modification on array. Besides return the length of array without duplicates, I still have to change the order of digits in the array.

Analysis

Considering the size of an array cannot change, and the clarification in the example said “It doesn’t matter what values are set beyond the returned length”, so what I have to do is move the digit towards if it didn’t show up before and put the repeated digit backward.
Obviously, the first digit is unchanged no matter how does array look like since the array is sorted. We can start from the second one whose index is 1.
We can use two cursors: index and i, and both of index and i starts from the value of 1. Then we set a loop, when we get into the loop, compare the nums[i] with nums[i-1], if they are the same, i move to the next digit while index doesn’t move, otherwise the nums[index] will be updated with the value of nums[i] and both of i and index move to the next digit.
The advantage of this method is we can guarantee that the order before the index is always right and no duplicates.

Right Code

public int removeDuplicates(int[] nums) {
    int index = 1;
    for (int i = 1; i < nums.length; i++){
        if (nums[i] == nums[i-1]){
            continue;
        }
        nums[index] = nums[i];
        index++;
    }
    return index;
}