How to Remove Duplicates from an Array
Removing duplicates from an array is one of the most common problems in Data Structures and Algorithms (DSA).
An array may contain the same value multiple times, but sometimes we need to keep only one occurrence of each value.
For example:
Input:
[10, 20, 10, 30, 20, 40, 30]
After removing duplicates:
Output:
[10, 20, 30, 40]
This problem teaches several important programming concepts, including:
Array traversal
Hash sets
Sorting
Two-pointer techniques
Maintaining order
Time complexity
Space complexity
In this article, we will explore several approaches and learn which one is most efficient for different situations.
Problem Statement
Given an array containing duplicate elements, remove the duplicates and return an array containing only unique values.
Example
Input:
[1, 2, 2, 3, 4, 4, 5]
Output:
[1, 2, 3, 4, 5]
Another example:
Input:
[5, 5, 5, 10, 10, 20]
Output:
[5, 10, 20]
What Does "Remove Duplicates" Mean?
Consider:
[10, 20, 10, 30, 20]
The values 10 and 20 appear more than once.
We only want to keep one occurrence:
[10, 20, 30]
If the original order matters, the first occurrence should normally be preserved.
For example:
Input:
[30, 10, 20, 10, 30]
Output:
[30, 10, 20]
The order of the first occurrences is preserved.
Approach 1: Using a Set
The simplest approach is to use a Set.
A Set stores unique values.
For example:
Input:
[10, 20, 10, 30, 20]
Set:
{10, 20, 30}
The duplicate values are automatically removed.
Python Solution Using Set
def remove_duplicates(arr):
return list(set(arr))
numbers = [10, 20, 10, 30, 20, 40]
result = remove_duplicates(numbers)
print(result)
A possible output is:
[40, 10, 20, 30]
However, there is an important issue.
A normal set should not be relied upon when the original ordering of elements is important.
If order must be preserved, use a different approach.
Python Set While Preserving Order
def remove_duplicates(arr):
seen = set()
result = []
for number in arr:
if number not in seen:
seen.add(number)
result.append(number)
return result
numbers = [10, 20, 10, 30, 20, 40]
print(remove_duplicates(numbers))
Output:
[10, 20, 30, 40]
Here:
seen
stores values that have already appeared.
The algorithm checks each element before adding it to the result.
How the Algorithm Works
Consider:
[10, 20, 10, 30, 20]
Initially:
seen = {}
result = []
Process 10:
seen = {10}
result = [10]
Process 20:
seen = {10, 20}
result = [10, 20]
Process the second 10:
10 is already in seen
So it is skipped.
Process 30:
seen = {10, 20, 30}
result = [10, 20, 30]
Process the second 20:
20 is already in seen
So it is skipped.
Final result:
[10, 20, 30]
Complexity of the Set Approach
For an array containing n elements:
Time Complexity: O(n)
Each element is processed once, and set lookup is approximately O(1) on average.
The set and result array require additional memory:
Space Complexity: O(n)
Therefore:
Time: O(n)
Space: O(n)
This is usually the easiest and most practical solution when extra memory is allowed.
Approach 2: Using Sorting
Another approach is to sort the array first.
Consider:
[30, 10, 20, 10, 30]
After sorting:
[10, 10, 20, 30, 30]
Now duplicate values are next to each other.
We can traverse the sorted array and keep only values that are different from the previous value.
Python Sorting Solution
def remove_duplicates(arr):
if not arr:
return []
arr.sort()
result = [arr[0]]
for i in range(1, len(arr)):
if arr[i] != arr[i - 1]:
result.append(arr[i])
return result
numbers = [30, 10, 20, 10, 30]
print(remove_duplicates(numbers))
Output:
[10, 20, 30]
Important Difference
The sorting approach changes the order of the array.
Input:
[30, 10, 20, 10, 30]
Output:
[10, 20, 30]
If the original order must be preserved:
[30, 10, 20]
then sorting is not appropriate unless changing the order is acceptable.
Complexity of Sorting
Sorting generally requires:
O(n log n)
time.
The subsequent traversal requires:
O(n)
time.
Therefore:
Time Complexity: O(n log n)
Depending on the implementation, additional space requirements may vary.
Approach 3: Brute Force
We can also remove duplicates without using a Set.
The idea is to check whether the current element already exists in the result array.
def remove_duplicates(arr):
result = []
for number in arr:
if number not in result:
result.append(number)
return result
numbers = [10, 20, 10, 30, 20]
print(remove_duplicates(numbers))
Output:
[10, 20, 30]
This is easy to understand, but it is not very efficient.
The expression:
number not in result
requires a linear search through result.
Therefore, in the worst case:
Time Complexity: O(n²)
This approach is acceptable for learning but usually not preferred for large arrays.
Approach 4: In-Place Removal for Sorted Arrays
There is a special version of this problem where the array is already sorted.
For example:
[1, 1, 2, 2, 3, 4, 4]
We want:
[1, 2, 3, 4]
Since duplicates are already next to each other, we can use the two-pointer technique.
Two-Pointer Technique
We maintain two positions:
slow
fast
The fast pointer scans the array.
The slow pointer keeps track of the position where the next unique element should be placed.
Example:
[1, 1, 2, 2, 3, 4, 4]
↑
slow
↑
fast
When a new value is found, move slow forward and copy the value.
Python Two-Pointer Solution
def remove_duplicates_sorted(arr):
if not arr:
return 0
slow = 0
for fast in range(1, len(arr)):
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
return slow + 1
numbers = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates_sorted(numbers)
print(numbers[:length])
Output:
[1, 2, 3, 4]
How the Two-Pointer Method Works
Consider:
[1, 1, 2, 2, 3]
Initially:
slow = 0
fast = 1
Compare:
arr[fast] == arr[slow]
Both are 1, so the duplicate is ignored.
Move fast.
Now:
fast → 2
The value is different from arr[slow].
Move slow:
slow = 1
Then:
arr[slow] = arr[fast]
The array becomes conceptually:
[1, 2, 2, 2, 3]
Continue until the entire array is processed.
The unique portion is:
[1, 2, 3]
Why Is This Called Two Pointers?
Because two indexes move through the array:
slow
↓
[1, 1, 2, 2, 3, 4]
↑
fast
The fast pointer explores the array.
The slow pointer maintains the unique portion.
This pattern is extremely common in DSA.
Complexity of the Two-Pointer Approach
Because the array is already sorted, we only need one traversal.
Therefore:
Time Complexity: O(n)
The algorithm modifies the original array and uses only a few variables.
Therefore:
Space Complexity: O(1)
This makes it an excellent solution when:
The array is already sorted
Extra memory is not allowed
The problem specifically asks for an in-place solution
Java Solution Using HashSet
For an unsorted array, a HashSet can be used.
import java.util.*;
public class Main {
public static int[] removeDuplicates(int[] arr) {
LinkedHashSet<Integer> set =
new LinkedHashSet<>();
for (int number : arr) {
set.add(number);
}
int[] result =
new int[set.size()];
int index = 0;
for (int number : set) {
result[index] = number;
index++;
}
return result;
}
public static void main(String[] args) {
int[] numbers = {
10, 20, 10, 30, 20, 40
};
int[] result =
removeDuplicates(numbers);
System.out.println(
Arrays.toString(result)
);
}
}
Output:
[10, 20, 30, 40]
LinkedHashSet is used here because it preserves insertion order.
Java Two-Pointer Solution
For a sorted array:
public class Main {
public static int removeDuplicates(
int[] arr
) {
if (arr.length == 0) {
return 0;
}
int slow = 0;
for (
int fast = 1;
fast < arr.length;
fast++
) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1;
}
public static void main(String[] args) {
int[] numbers = {
1, 1, 2, 2, 3, 4, 4
};
int length =
removeDuplicates(numbers);
for (
int i = 0;
i < length;
i++
) {
System.out.print(
numbers[i] + " "
);
}
}
}
Output:
1 2 3 4
C++ Solution Using Set
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
vector<int> removeDuplicates(
const vector<int>& arr
) {
unordered_set<int> seen;
vector<int> result;
for (int number : arr) {
if (seen.find(number) ==
seen.end()) {
seen.insert(number);
result.push_back(number);
}
}
return result;
}
int main() {
vector<int> numbers = {
10, 20, 10, 30, 20, 40
};
vector<int> result =
removeDuplicates(numbers);
for (int number : result) {
cout << number << " ";
}
return 0;
}
Output:
10 20 30 40
C++ Two-Pointer Solution
For a sorted array:
#include <iostream>
#include <vector>
using namespace std;
int removeDuplicates(
vector<int>& arr
) {
if (arr.empty()) {
return 0;
}
int slow = 0;
for (
int fast = 1;
fast < arr.size();
fast++
) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1;
}
int main() {
vector<int> numbers = {
1, 1, 2, 2, 3, 4, 4
};
int length =
removeDuplicates(numbers);
for (int i = 0; i < length; i++) {
cout << numbers[i] << " ";
}
return 0;
}
Output:
1 2 3 4
JavaScript Solution Using Set
JavaScript provides a convenient way to remove duplicates using Set.
function removeDuplicates(arr) {
return [...new Set(arr)];
}
const numbers = [
10, 20, 10, 30, 20, 40
];
console.log(
removeDuplicates(numbers)
);
Output:
[10, 20, 30, 40]
This also preserves insertion order.
JavaScript Two-Pointer Solution
For a sorted array:
function removeDuplicates(arr) {
if (arr.length === 0) {
return 0;
}
let slow = 0;
for (
let fast = 1;
fast < arr.length;
fast++
) {
if (arr[fast] !== arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1;
}
const numbers = [
1, 1, 2, 2, 3, 4, 4
];
const length =
removeDuplicates(numbers);
console.log(
numbers.slice(0, length)
);
Output:
[1, 2, 3, 4]
Comparing the Approaches
ApproachTime ComplexityExtra SpacePreserves OrderBrute ForceO(n²)O(n)YesSet / HashSetO(n) averageO(n)Depends on implementationSortingO(n log n)DependsNoTwo PointersO(n)O(1)Yes, for sorted input
The best approach depends on the problem requirements.
Which Approach Should You Use?
If the array is unsorted:
Use a Set or HashSet.
O(n) average time
O(n) space
If the array is sorted:
Use the two-pointer technique.
O(n) time
O(1) space
If the interviewer requires in-place modification:
The two-pointer technique is usually the best choice for a sorted array.
If you simply need unique values in application code:
A built-in Set is often the simplest solution.
Edge Cases
A good solution should handle different inputs.
Empty Array
[]
Output:
[]
One Element
[10]
Output:
[10]
All Elements Are Duplicates
[5, 5, 5, 5]
Output:
[5]
No Duplicates
[1, 2, 3, 4]
Output:
[1, 2, 3, 4]
Negative Numbers
[-5, -2, -5, -10, -2]
Output:
[-5, -2, -10]
The Set-based approach handles negative values normally.
Common Interview Mistakes
1. Using Nested Loops Without Considering Complexity
A nested-loop solution can easily become:
O(n²)
For large arrays, this can be inefficient.
2. Sorting When Order Matters
Sorting:
[30, 10, 20, 10]
produces:
[10, 10, 20, 30]
But if the expected unique array is:
[30, 10, 20]
sorting is not appropriate.
3. Using Two Pointers on an Unsorted Array
The two-pointer technique for removing duplicates relies on duplicates being adjacent.
For example:
[10, 20, 10, 30]
The duplicates are not next to each other.
Therefore, simply applying the sorted-array two-pointer algorithm will not correctly solve the general problem.
4. Forgetting the Empty Array
Always consider:
if not arr:
return []
when writing a function that accesses the first element.
Interview Explanation
If an interviewer asks how you would remove duplicates from an unsorted array, you can say:
I would traverse the array once while maintaining a Set containing values that have already appeared. For each element, I check whether it exists in the Set. If it does not, I add it to the Set and append it to the result. This gives O(n) average time complexity and O(n) additional space.
For a sorted array, you can say:
Since the array is sorted, duplicate elements are adjacent. I can use two pointers: a fast pointer to scan the array and a slow pointer to maintain the position of the next unique element. This allows duplicates to be removed in place with O(n) time and O(1) extra space.
Important DSA Pattern: Two Pointers
The sorted-array solution introduces the two-pointer pattern.
The general structure is:
slow = 0
for fast from 1 to n-1:
if condition:
slow += 1
arr[slow] = arr[fast]
This pattern appears in many DSA problems.
Examples include:
Remove duplicates
Move zeros
Remove a specific element
Partition arrays
Merge sorted arrays
Find pairs
Sliding-window variations
Learning the two-pointer technique will help solve many array and string problems efficiently.
Final Summary
Removing duplicates from an array can be solved in several ways.
For an unsorted array, a Set provides a simple and efficient solution:
Input
↓
Traverse Array
↓
Check Set
↓
New Value?
↓
Add to Set
↓
Add to Result
For a sorted array, the two-pointer technique provides an optimal in-place solution:
Sorted Array
↓
Fast Pointer
↓
Compare Values
↓
New Value?
↓
Move Slow Pointer
↓
Store Unique Value
The key complexities are:
Set Approach:
Time → O(n) average
Space → O(n)
Two-Pointer Approach:
Time → O(n)
Space → O(1)
The most important lesson is not just how to remove duplicates, but how to choose an algorithm based on the input constraints.
If the array is unsorted and extra memory is acceptable, use a Set.
If the array is sorted and the problem requires an in-place solution, use the two-pointer technique.
These patterns are fundamental building blocks for solving more advanced DSA problems.