Remove Duplicates from Sorted Array 2

Hey guys👋

In this article you will learn how to solve the Remove Duplicates from Sorted Arrays 2 on Leetcode and I will solve the question using 2 methods which are Hash Tables and the Two Pointer Method.

Stay Calm and Let's get in✨

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,,]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Solution

Two Pointer Method

This method requires us to compare three values of the array and check if a value appears three times and if it appears three times we will remove the middle value of the three values we are comparing. So let's try it.

Declare the middle pointer.
```
let p2 = 1;
```

Loop through the nums array and do a check with three values to see if they are the same.

 for (let p1 = 0; p2 < nums.length; p1++) {
     if((nums[p1] == nums[p2]) && nums[p2] == nums[p2 + 1]) {
     } 
 }

If the three values are the same we will need to remove one of it since a value cannot appear more than twice.

 for (let p1 = 0; p2 < nums.length; p1++) {
     if((nums[p1] == nums[p2]) && nums[p2] == nums[p2 + 1]) {
         nums.splice(p2, 1);
     }
 }

After removing it we will need to reduce the index since we deleted a value from the array.

 for (let p1 = 0; p2 < nums.length; p1++) {
     if((nums[p1] == nums[p2]) && nums[p2] == nums[p2 + 1]) {
         nums.splice(p2, 1);
         p1--;
     }
 }

Finally, if this condition is not met we will need to increment our pointer and check new values.

  for (let p1 = 0; p2 < nums.length; p1++) {
      if((nums[p1] == nums[p2]) && nums[p2] == nums[p2 + 1]) {
          nums.splice(p2, 1);
          p1--;
      } else {
          p2++;
      }
  }

The Compilation of the code above can be found below.

let p2 = 1;

    for (let p1 = 0; p2 < nums.length; p1++) {
        if((nums[p1] == nums[p2]) && nums[p2] == nums[p2 + 1]) {
            nums.splice(p2, 1);
            p1--;
        } else {
            p2++;
        }
    }

Time Complexity: O(n)
Space Complexity: O(1)

Remove Duplicates from Sorted Array 2 Solution.JPG

Conclusion

I hope you have learnt a lot from this article and your contribution is also highly welcomed because we get better by learning from others, you can reach out to me on Twitter here . Watch out for more helpful contents on Data Structures and Algorithm from me.

Don't forget to Like, share and subscribe for more articles in this series called Solutions to Data Structures and Algorithm Questions on Leetcode.

Enjoy 🎉

Arimoro Olamilekan Ezekiel's Blog

Arimoro Olamilekan Ezekiel's Blog

Remove Duplicates from Sorted Array 2

Solution

Two Pointer Method

Conclusion