Took a while to solve this Leetcode problem. Remove Duplicates From Sorted Array II
Tags: leetcode, tutorial, codenewbie, algorithms
Published: 2020-05-10 21:55:21

I must confess this question took me a while as a beginner. This is a medium [Leetcode 80](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/) question. This is similar to [Leetcode 26](https://leetcode.com/problems/remove-duplicates-from-sorted-array) 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]
(https://miro.medium.com/max/1400/1*MycigMpBfUepc-B1IVf5bA.png)
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;

}
```
<h3><b>THE CORRECT CONCEPT</b></h3>
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.