Remove Duplicates from Sorted Array

Question

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.

Example:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Analyzation

Double Pointer.

First of all, note that the array is ordered, so the repeated elements must be adjacent. The requirement to delete duplicate elements is actually to move non-duplicate elements to the left side of the array. Consider using two pointers, one is denoted as p in the front, and the other is denoted as q in the back. The algorithm flow is as follows:

Compare whether the elements at positions p and q are equal. If equal, q is shifted backward by 1 bit If they are not equal, copy the element at position q to position p+1, shift p by one bit and q by one bit Repeat the above process until q is equal to the length of the array.

Return p + 1, which is the new array length.

Consider this image:

The Code

 public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    
    int p = 0;
    int q = 1;
    
    while(q < nums.length){
        if(nums[p] != nums[q]){
            nums[p + 1] = nums[q];
            p++;
        }
        q++;
    }
    
    return p + 1;
}

Time & Space Complexity

• Time Complexity: Since we create a loop so it is O(n).
• Space Complexity: Since we do this in place, the Space Complexity is O(1).

Optimization

Consider this situation: At this time, there are no duplicate elements in the array. According to the above method, nums[p] is not equal to nums[q] during each comparison, so the element pointed to by q will be copied in place. This operation is actually unnecessary.

Therefore, we can add a small judgment, when q - p > 1, then copy. Code is here:

public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    
    int p = 0;
    int q = 1;
    
    while(q < nums.length){
        if(nums[p] != nums[q]){
            if(q - p > 1){
                nums[p + 1] = nums[q];
            }
            p++;
        }
        q++;
    }
    return p + 1;
}

Time & Space Complexity

• Time Complexity: Since we create a loop so it is O(n).
• Space Complexity: Since we do this in place, the Space Complexity is O(1).