Remove Duplicates from Array

Problem Statement

Given an array of integers, the task is to remove the duplicates from the array.

Method – 1 (Using Sorting)

Intuition:

Sorting will help in grouping duplicate elements together.

Input array: 1 2 3 2 2 3 4
Sorted array: 1 2 2 2 3 3 4 (all 2’s and 3’s are grouped together). 

Now the problem is to remove duplicates from the sorted array.

Solution 1 (Using extra space)

• Sort the given array.
• Create an auxiliary array to store the unique elements and also maintain the count of unique elements.(here we will iterate over the sorted array and will put the first occurrence of each element in the auxiliary array and also maintain an integer to get the count of these unique elements which will also tell us about the index where the next element should be placed).
• Copy elements from auxiliary array to given array.

C/C++ Code

int removeDuplicates(int arr[], int n) {
    if(n == 0 || n == 1)
        return n;
    sort(arr, arr+n);
    int temp[n];       
    int i = 0, j = 0;      
    temp[j++] = arr[i++];
    for( ; i<n; i++){
        if(arr[i] != arr[i-1]){
            temp[j++] = arr[i];
        }
    }
    for(i=0; i<j; i++){
            arr[i] = temp[j];
    }
    return j;
}

Java Code

public static int removeduplicates(int arr[], int n){
    if (n == 0 || n == 1) {
        return n;
    }
    Arrays.sort(arr);  
    int[] temp = new int[n];
    int i = 0, j = 0;
    temp[j++] = arr[i++];
    for ( ; i < n - 1; i++) {
        if (arr[i] != arr[i-1]) {
            temp[j++] = arr[i];
        }
    }
    for (i = 0; i < j; i++) {
        arr[i] = temp[i];
    }
    return j;
}

Python Code

def removeDuplicates(arr, n):
    if n == 0 or n == 1:
        return n
    arr.sort();
    temp = list(range(n))
    j = 0
    temp[j] = arr[0]    j+=1
    for i in range(1, n):
        if arr[i] != arr[i-1]:
            temp[j] = arr[i]
            j += 1
           
    for i in range(0, j):
        arr[i] = temp[i]

    return j

• Time complexity will be O(NlogN) because we have used sorting.
• Space complexity will be O(N) using an extra array.

Solution 2 (Without using extra space)

The approach is the same as the above solution: just don’t use the extra array instead do in-place swaps.

We are using an integer to have the count of unique elements which will also tell us about the position where the new element should be placed in the same array.

So starting from j = 0 indicates no unique elements are there and as we will iterate if we encounter any new element we put that element in jth position and will increase j.

C/C++ Implementation

int removeDuplicates(int arr[], int n) {
    if(n == 0 || n == 1)
        return n;
    sort(arr, arr+n);       
    int j = 0;      
    for(int i=1; i<n; i++){
        if(arr[i] != arr[i-1]){
          arr[++j]=arr[i];
        }
    }
    return j;
}

Java Implementation

public static int removeduplicates(int arr[], int n){
    if (n == 0 || n == 1) {
        return n;
    }
    Arrays.sort(arr);  
    int j = 0;
    for ( int i = 0; i < n ; i++) {
        if (arr[i] != arr[i-1]) {
            arr[++j] = arr[i];
        }
    }
    return j;
}

Python Implementation

def removeDuplicates(arr, n):
    if n == 0 or n == 1:
        return n
    arr.sort();
    j = 1
    for i in range(1, n):
        if arr[i] != arr[i-1]:
            arr[j] = arr[i]
            j += 1
    return j

• Time complexity will be O(NlogN) because we have used sorting.
• Space complexity will be O(N) using an extra array.

Method – 2 (Use of HashMaps)

We know we can use hashmaps when we need to know whether some element is present in it in O(1).

So while traversing the array we will store the elements in a hashmap.

And like approaches explained above we will place unique elements by checking whether the current element is already present in the hashmap or not.

C/C++ Code For HashMaps

int removeDuplicates(int arr[], int n) {
    if(n == 0 || n == 1)
        return n;       
    int j = 0;       unordered_map<int,int> mp;   
    for(int i=0; i<n; i++){
        if(mp.find(arr[i])==mp.end()){            arr[j++] = arr[i];        }
    }
    return j;
}

Java Code For HashMaps

public static int removeduplicates(int arr[], int n){
    if (n == 0 || n == 1) {
        return n;
    }
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    int j = 0;
    for (int i=0; i < n; i++) {
        if (map.containsKey(arr[i])==0) {
            map.put(arr[i], 1);             arr[j++] = arr[i];
        }
    }
    return j;
}

Python Code For HashMaps

def removeDuplicates(arr, n):
    if n == 0 or n == 1:
        return n    mp = {i : 0 for i in arr}
    j = 0
    for i in range(0, n):
        if mp[arr[i]]==0:
            arr[j] = arr[i]
            j += 1            mp[arr[i]] = 1
    return j

• Time complexity will be O(N) because of the use of hashmaps.
• Space complexity will be O(N) using a hashmap.

---

Practice Problems

Remove Duplicates From Sorted Arrays
Remove Element From An Array

FAQs

Q.1: How do you find duplicates in an array?

Ans: For finding duplicates we can use our hashmaps, and we can also find duplicates by sorting the array.

Q.2: How do you remove duplicates from an unsorted array in place?

Ans: We can use hashmaps to maintain the frequency of each element and then we can remove the duplicates from the array.