DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

codechunker
codechunker

Posted on

Took a while to solve this Leetcode problem. Remove Duplicates From Sorted Array II

I must confess this question took me a while as a beginner. This is a medium Leetcode 80 question. This is similar to Leetcode 26 where you are simply asked to remove all duplicates in an array. The tweak in Leetcode 80 is that the highest duplicate a number in array can have is two e.g [1,1,1,2,2,3] should turn to [1,1,2,2,3]. See problem description below:

problem description
This problem took me a while not because i could not solve it with any method I wanted, but I wanted to solve it the way it was described in the question i.e solving it in-place in O(1) space complexity.

See below the rubbish I was trying to do🀣🀣🀣. PLEASE DON’T TRY THIS AT HOME. I won't even bother trying to explain what i was trying to do but if you can understand it, fine and good.

public static int removeDuplicates(int[] nums) {
    //111223 => 11223
    int count = 0;
    int elementCount = 1;

    for (int i = 0; i < nums.length; i++) {
        if (i + 1 < nums.length) {

            if (nums[i] == nums[i + 1] && elementCount < 3) {
                elementCount++;
                nums[count] = nums[i];
                count++;
            }else if (nums[i] == nums[i+1] && elementCount >= 3){
                elementCount++;
                continue;
            }else if (nums[i] != nums[i+1] && elementCount >=3){
                elementCount = 1;
                int temp = nums[i+1];
                nums[count] = temp;
                nums[i+1] = -1;
                count++;
            }else if (nums[i] != nums[i+1] && elementCount < 3){
                elementCount = 1;

                if (nums[i] == -1){
                    nums[count] = nums[i+1];
                    elementCount = 3;
                }

                else nums[count] = nums[i];
                count++;
            }
        }

    }

    return count;

}

THE CORRECT CONCEPT

Since the problem says the maximum duplicates you can have for a number is two (2) and the problem must be solve in-place i.e don’t create a new array rather manipulate the given array. The concept is as follows;

Keep a counter index(indexCount)from the third index (3) this is to be incremented. You do this because no matter what, the first two indices will always be correct. it doesn’t matter if they are the same or different.

From the third index, start comparing the current index to two indices before it. If they are not equal, put the current element (nums[i]) into the current indexCount value and then increment indexCount. Remember, if they are equal, that means the current element is now 3 which violates condition that the maximum duplicate should be 2. The code is shown below:

public static int removeDuplicates(int[] nums) {
    int indexCount = 2;
    for (int i = 2; i < nums.length; i++) {
        if (nums[i] != nums[indexCount-2]) {
            nums[indexCount] = nums[i];
            indexCount++;
        }
    }
    return indexCount;
}

The runtime of the algorithm above is O(n) and the space complexity is O(1) which makes it very efficient especially in terms of space complexity.

Remember always think outside the box
Thank you for reading. Please leave a comment or suggestion.

Top comments (0)

We are hiring! Do you want to be our Senior Platform Engineer? Are you capable of chipping in across sysadmin, ops, and site reliability work, while supporting the open source stack that runs DEV and other communities?

This role might just be for you!

Apply now