Remove duplicate elements from sorted Array

Given a sorted array a[] of size n, delete all the duplicated elements from a[] & modify the array such that only distinct elements should be present there.

Note:
1. Don’t use set or HashMap to solve the problem.
2. You must return the modified array size where only distinct elements are present in the array, the driver code will print all the elements of the modified array.

Example 1:

Input:
N = 5
Array = {2, 2, 2, 2, 2}
Output: 
1
Explanation: After removing all the duplicates only one instance of 2 will remain i.e. {2} so modify array will contains 2 at first position and you should return 1 after modify the array.

Example 2:

Input:
N = 4
Array = {1, 2, 2, 4}
Output: 3
Explanation: After removing all duplicates modify array will contains {1, 2, 4} at first 3 positions so you should return 3 after modify the array.

Solve :

Here you need the common two pointer approach if you want to solve the problem in O(N) which would be the time complexity and O(1) which would be the space complexity. You have to select only those numbers which are unique. Right ! then this make sense that you will be avoid all the duplicates. Now, think the first number will always be unique. I think you are also agree with me. Then when the another number will not match with the first number it will be the second number and we will increment our count and now we will match the second number with other to get another unique number which will be the third and so on. That’s it

Here is the code in C++ :

 int remove_duplicate(int a[],int n){

        int i = 0,j=1,count = 1;
        while(j<n){
            if(a[i] != a[j]){
                ++i;
                a[i] = a[j];
                ++count;
            }
            ++j;
        }
        return count;
    }

Happy Coding !!