Remove Duplicates from Array

Problem Statement

Given an array of integers, we have to remove duplicates from array such that each element in the array appears only once (all the values in the array should become unique).

Example

Input : [1,2,2,3,4,4,4,5,5]

Output : [1,2,3,4,5]

Explanation

As we can see the frequency of all the elements

Element	Frequency
1	1
2	2
3	1
4	3
5	2

After removing the duplicates, the frequency of all the elements became 1, so all the duplicate elements have been removed.

Element	Frequency
1	1
2	1
3	1
4	1
5	1

So the output is [1,2,3,4,5]

Constraints

$1 <= N <= 10^6$
$1 <= A[i] <= 10^5$

Approach 1 - Using Extra Space

This is the Brute-Force method to remove duplicates from array. In this method, we will be using extra space.

Algorithm:

Sort the array
Create a resultant array named res, to store the modified array
Run a loop from i=0 to i=n-2
if a[i]!=a[i+1], then push a[i] into res array
add the a[n-1] element into res array
Finally return the resultant array

C++ Implementation

Java Implementation

Python Implementation

Complexity Analysis

Time Complexity Analysis

In the first step, we are sorting the array which takes $O(NlogN)$ time
Then we are running the loop from 1 to n-1 which takes $O(N)$ time

So the total worst case time complexity for this approach to remove duplicates from array is $O(NlogN)+O(N) = O(NlogN)$

Auxilary Space Analysis In this approach we are using the resultant array for storing the unique elements, so it uses $O(N)$ auxiliary space to remove duplicates from array.

Time Complexity: $O(NlogN)$
Auxilary Space: $O(N)$

Approach 2 - Using Constant Extra space

In this method, we will not use any auxiliary space, we will just modify the given array such that the k elements from the starting are the unique elements, and the rest are duplicates and we will return the value of k. So in this way we can remove duplicates from array.

Algorithm:

Sort the array
We know that the first element will always be unique, so we maintain a pointer named k, which will start from 1 and keep the track of the unique elements.
Run a loop from i=0 to i=n-2
If a[i]!=a[i+1], then a[k]=a[i] and k++
else continue;
add the a[n-1] element into res array
Finally return the value of k, which is now the total number of unique elements in the array, so we will print the elements present in the index from i=0 to i=k-1

C++ Implementation

Java Implementation

Python Implementation

Complexity Analysis

Time Complexity Analysis

In the first step, we are sorting the array which takes $O(NlogN)$ time
Then we are running the loop from 0 to n-2 which takes $O(N)$ time

So the total worst case time complexity for this approach to remove duplicates from array is $O(NlogN)+O(N) = O(NlogN)$

Auxilary Space Analysis In this approach we are using only one variable i.e. k, so ultimately we are using only constant extra space which is $O(1)$

Time Complexity: $O(NlogN)$
Auxilary Space: $O(1)$

Approach 3 - Using a Set

In this method, we are going to use the Set Data structure to remove duplicates from array. Finally, we will modify the given array such that the k elements from the starting are the unique elements, and we will return k which is the total number of unique elements.

Note: Set is a data structure that stores only one occurrence of each element inserted into it.

Algorithm:

Create a set named s
Insert all the elements of the array into the set
Maintain a pointer named k and initialize it with 0
Start traversing the set and modify the array as a[k]=x and k++, where x is the element in the set
Finally return the value of k, which is now the total number of unique elements in the array, so we will print the elements present in the index from i=0 to i=k-1

C++ Implementation

Java Implementation

Python Implementation

Complexity Analysis

Time Complexity Analysis

In the first step, we are inserting all the elements of the array into the set by running a loop from i=0 to i=n-1 which will take $O(N)$ time.
Internally, the set uses hashing and takes $O(NlogN)$ time for sorting the elements.
Finally, we are traversing the set which will take $O(N)$ time in the worst case (if every element is unique)

So the total worst case time complexity for this approach to remove duplicates from array is $O(N)+O(NlogN)+O(N) = O(NlogN)$

Auxilary Space Analysis In this approach, we are using a set and we are inserting all the elements of the array into the set. So we are using $O(N)$ auxiliary space in this approach.

Time Complexity: $O(NlogN)$
Auxilary Space: $O(N)$

Approach 4 - Using indexOf() and filter() methods in Javascript

In this approach, we will see how we can remove duplicates from array by using indexOf() and filter() methods in JavaScript.

Note: The indexOf() method returns the position of the first occurrence of an element in the array.

Note: The filter() method returns a new array that is filled with all the elements that passed the test provided by the function.

Algorithm

Create a new array named result
Use filter() method to include only elements whose indexes match their indexOf() values
Print the result array

Javascript Implementation

Complexity Analysis

Time Complexity Analysis

In the first step, we are traversing the array which will take $O(N)$ time.
Inside the loop, we are using the indexOf() method, which will take $O(N)$ time.

So the total worst-case time complexity for this approach to remove duplicates from array is $O(N^2)$

Auxilary Space Analysis In this approach, we are using the resultant array to store the result. So we are using $O(N)$ auxiliary space in this approach.

Time Complexity: $O(N^2)$
Auxilary Space: $O(N)$

Approach 5 - Using forEach() and include() methods in Javascript

In this approach, we will see how we can remove duplicates from array by using forEach() and include() methods in JavaScript.

Note: The forEach() method calls the function for traversing each element in the array.

Note: The include() method returns true if a particular element is present in the array, else returns false.

Algorithm

Create a new array named result
Traverse the given array by using the forEach() method and use the include() method on the resultant array which returns true if an element is present in an array, otherwise returns false
Print the result array

Javascript Implementation

Complexity Analysis

Time Complexity Analysis

In the first step, we are traversing the array using forEach loop which will take $O(N)$ time.
Inside the loop we are using the includes() method, which will take $O(N)$ time.

So the total worst-case time complexity for this approach to remove duplicates from array is $O(N^2)$

Auxilary Space Analysis In this approach, we are using the resultant array to store the result. So we are using $O(N)$ auxiliary space in this approach.

Time Complexity: $O(N^2)$
Auxilary Space: $O(N)$

Conclusion

In this quick tutorial, we have discussed 5 different approaches to remove duplicates from array, of which 2 are specific to Javascript language

In Approach 1, we sorted the array and used $O(N)$ extra space
In Approach 2, we sorted the array but we used only $O(1)$ extra space
In Approach 3, we used Set data structure, and used $O(N)$ extra space
In Approach 4, we learned how to remove duplicates in Javascript by using indexOf() and filter() methods
In Approach 5, we learned how to remove duplicates in Javascript by using forEach() and include() methods

Frequently asked questions (FAQs)

Q: How can we remove duplicates from an unsorted array?

A: We can use a hashmap that maintains the frequency of each element, and then by letting only 1 occurrence of each element into the array, we can remove duplicates from array.

Q: What can be the best time complexity for removing the duplicates?

A: By using an unordered set, we can remove duplicates from array in only O(N) time complexity and O(N) auxiliary space.