26. Remove Duplicates from Sorted Array¶

Remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Return the number of unique elements in nums.

Intuition¶

• A number is unique if nums[i] != nums[i-1]
• If its not unique we can overwrite it with the next greater element.

Approach¶

• Start from the beginning with i=0 & j=0
• i is fast points to current element & j is slow pointing to the previous element.
• Only if the previous pointed element is not equal to the current element we increase j.
• write current value in its place

Complexity¶

• Time complexity : \(\text{O}(n)\)
• we iterate the array only once
• Space complexity : \(\text{O}(1)\)
• we do operation in-place, no extra space needed

Code¶

public int removeDuplicates(int[] nums) {
    int j = 0;

    for (int i = 0; i < nums.length; ++i) {
        // If the element are not equal only then add to array
        if(nums[i] != nums[j]) {
            nums[++j] = nums[i];
        }
    }
    return j+1;
}

Alternate Solution

Count the number of places to shift each element

public int removeDuplicates(int[] nums) { 
    int shiftPlacesBy = 0; 
    for (int i = 1; i < nums.length; ++i) { 
        // if elements are equal we increase the shift count by
        if(nums[i] == nums[i-1]) { 
            shiftPlacesBy++; 
            continue; 
        } 
        nums[i - shiftPlacesBy] = nums[i]; 
    } 
    return nums.length - shiftPlacesBy; 
} 

• we iterate the array only once
• we do operation in-place, no extra space needed

Comments