yaox023
yaox023's blog

yaox023's blog

Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

yaox023's photo
yaox023
·Oct 3, 2022·

3 min read

Subscribe to my newsletter and never miss my upcoming articles

Let's see the leetcode problem Remove Duplicates from Sorted Array. There are 2 version of this problem. Let see them one by one.

The first one is Remove Duplicates from Sorted Array.

Let's see an example. If the array is [1,2,2,3,3,4,5], we know there are 2 of element 2, 2 of element 3, so we want to remove these duplicates.

For sure, we will iterate the whole array. Say we are now at index 2 and we know it is a duplicate, what should we do?

 0 1 2 3 4 5 6
[1,2,2,3,3,4,5]

Actually, my first idea is to delete this element by move all the element on the right to left.

 0 1 2 3 4 5 6
[1,2,2,3,3,4,5] =>
       - - - -
[1,2,3,3,4,5,5]
     - - - -

But in this way, we need a another loop for this, so the time complexity would be O(n^2).

So the more effcient way is to use a two-pointers solution. One point is used to iterate the whole array, another pointer is used to store the valid position for this array. So the process may become this.

 0 1 2 3 4 5 6

     j
[1,2,2,3,3,4,5]
     i
[1,2,2,3,3,4,5]

=>

       j
[1,2,2,3,3,4,5]
     i
[1,2,2,3,3,4,5]

=>

         j
[1,2,2,3,3,4,5]
       i
[1,2,3,3,3,4,5]

The idea is, when we know current element a duplicate, we will just ignore this element. And if current element is the unique element, then we store it in the valid position.

So let see the code.

function removeDuplicates(nums: number[]): number {
    let i = 1;
    for (let j = 1; j < nums.length; j++) {
        if (nums[j] !== nums[j-1]) {
            nums[i++] = nums[j]
        }
    }
    return i;
};

Now let see the harder one Remove Duplicates from Sorted Array II.

The hard part is that we can's know if current element is duplicate just by comparing current element with previous one. We need another variable to keep logs of the times we saw the same element. Other logic is pretty the same.

To make to more simple, I split the logic into two parts. The first part will find all the invalid elements, and set them with a placeholder value. Then a second loop is used to store all the valid element by the two pointer approach.

function removeDuplicates(nums: number[]): number {
    let pre = nums[0];
    let count = 1;
    for (let i = 1; i < nums.length; i++) {
        if (count === 2) {
            if (nums[i] === pre) {
                nums[i] = NaN;
            } else {
                count = 1;
                pre = nums[i];
            }
        } else {
            if (nums[i] === pre) {
                count++;
            } else {
                count = 1;
                pre = nums[i];
            }
        }
    }

    let i = 0;
    for (let j = 0; j < nums.length; j++) {
        if (!Number.isNaN(nums[j])) {
            nums[i++] = nums[j];
        }
    }

    return i;
};

This second problem defines 2 as the standard for invalid element. Actually this solution can be used with any number standard.

 
Share this