Remove Duplicates from Array

Given a sorted array (in ascending order) remove the duplicates from them .

you should not use any extra memory.

So to remove in place , you need to move all the unique elements to the left of the array.

So if there are k unique elements in an array of length n,

the first k elements will be the unique elements and the rest of the elements can be ignored.

For example,

Given the input:

Input: nums = [0,0,1,1,1,2,2,3,3,4]

The output array should be :

nums = [0,1,2,3,4]

You should return the number of unique elements which in the above case is 5.

Try out the solution here:

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Solution:

Use two pointer approach.

This is one of the patterns which you repeatedly use to solve problems.

In this case , create two pointers one to point to the last unique element in the array and another to navigate through the array.

Initially both these pointers will be pointing to the first element.

Whenever you see that the current element and the last unique element is not the same , you keep incrementing the current pointer.

And then move the last unique pointer by one place and assign the element pointed by the current pointer to the last unique pointer.

Again repeat the steps until all the elements are traversed.

Finally return the number of unique elements which is equal the last unique pointer index+1.

Here is the code:

class Solution {
    public int removeDuplicates(int[] nums) {
        
        
    int unique = 0;
        
        int current = 0;
        
        
        while(current < nums.length){
            
            
            while(current < nums.length && nums[unique] == nums[current]){
                
                
                current++;
            }
            
            if(current < nums.length){
                
                unique++;
                
                nums[unique] = nums[current++];
            }
            
        }
        
        return unique+1;
        
    }
}

Time complexity:

You traverse through all the elements in the array once so time complexity is O(n)

Space complexity:

There is no extra space complexity as we do the removal in place.

That’s it!