Remove Duplicates from Sorted Array

Hello guys👋

In this article you will learn how to solve the Remove Duplicates from Sorted Arrays 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 the duplicates in-place such that each unique element appears only once. 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,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 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,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Solution

Using Hash Tables

Set up a map which is an empty object, then store it in a variable called map.
```
let map = {};
```
Loop through the array and set the values to the map created above.
While looping through the array and setting the values to the map, we will check for any value that appears more than once and use the splice method to remove it.
```
for(let i = 0; i < nums.length; i++) {
  if(map[nums[i]]) {
    nums.splice(i,1);
  } 
}
```

Since we are removing the duplicate we will need to reduce the index of the values of the array.

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

We will also set the values that are unique as 1 in the map

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

Finally, since the question requires us to return the length of the array. let's return the length.

return nums.length;

The Compilation of the code for the Hash Table Method is below.

let map = {};

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

  return nums.length;

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

Two Pointer Method

This method requires us to compare two values of the array and check if they are the same or not. So let's try it.

Declare a pointer 1 that will be for the first value.
```
let pointer1 = 0;
```
Let's now loop through the array and check the values using pointer 1 declared outside the loop but increments in the loop and the pointer 2 declared in the loop.

If the value of pointer 1 and 2 is not the same then we will increment and check the next set of values.

let pointer1 = 0;

  for(let pointer2 = 1; pointer2 < nums.length; pointer2++) {
      if (nums[pointer1] !== nums[pointer2]) {
          pointer1++;
          nums[pointer1] = nums[pointer2];
      }
  }

The Final step is to return the length of the array after removing the duplicates. And since we are checking with pointers, the value of pointer 1 will be the length of the arrays without duplicates.
```
  return pointer1+1;
```

The Compilation of the Code for the Two Pointer Method is below.

   // Two Pointers
    let pointer1 = 0;

    for(let pointer2 = 1; pointer2 < nums.length; pointer2++) {
        if (nums[pointer1] !== nums[pointer2]) {
            pointer1++;
            nums[pointer1] = nums[pointer2];
        }
    }

    return pointer1+1;

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

Remove Duplicates From Sorted Array 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