.png)
Remove Duplicate Elements from an Array
Problem Statement
Given an array of elements, the task is to remove duplicate elements so that each element appears only once.
Important Notes
- The relative order of elements should be preserved
- The result should contain only unique elements
- Duplicates are extra occurrences of the same value
Understanding the Problem
Example 1
Input Array: [1, 2, 3, 2, 1, 4]
Output Array: [1, 2, 3, 4]
Example 2
Input Array: [5, 5, 5, 5]
Output Array: [5]
Why This Problem Is Important
This problem helps in understanding:
- Duplicate detection
- Use of auxiliary data structures
- Array reconstruction
- Real-world data cleaning techniques
It is commonly used in:
- Data preprocessing
- Removing redundant records
- Optimizing storage
- Hashing-based problems
Approaches to Solve the Problem
Approach 1: Using an Auxiliary Data Structure (Recommended)
- Use a Set or Hash Table
- Traverse the array
- Add elements to the set if they are not already present
- Store the unique elements in a new array
This approach preserves order and is efficient.
Step-by-Step Algorithm
- Create an empty set seen
- Create an empty array result
- Traverse the original array
- For each element:
- If element is not in seen:
- Add it to seen
- Add it to result
- If element is not in seen:
- Print the result array
Pseudocode
seen = empty set
result = empty array
for each element in array:
if element not in seen:
add element to seen
add element to result
print result
Dry Run Example
Array = [1, 2, 3, 2, 1, 4]
1 → not in set → add
2 → not in set → add
3 → not in set → add
2 → already in set → skip
1 → already in set → skip
4 → not in set → add
Result = [1, 2, 3, 4]
Time and Space Complexity
| Metric | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(n) |
Extra space is used to track duplicates.
Language-wise Implementation
C Implementation
#include
int main() {
int arr[] = {1, 2, 3, 2, 1, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int temp[100];
int size = 0;
for(int i = 0; i < n; i++) {
int isDuplicate = 0;
for(int j = 0; j < size; j++) {
if(arr[i] == temp[j]) {
isDuplicate = 1;
break;
}
}
if(!isDuplicate) {
temp[size++] = arr[i];
}
}
printf("Array after removing duplicates: ");
for(int i = 0; i < size; i++) {
printf("%d ", temp[i]);
}
return 0;
}
Output
Array after removing duplicates: 1 2 3 4
C++ Implementation
#include
#include
using namespace std;
int main() {
int arr[] = {1, 2, 3, 2, 1, 4};
int n = sizeof(arr) / sizeof(arr[0]);
unordered_set seen;
cout << "Array after removing duplicates: ";
for(int i = 0; i < n; i++) {
if(seen.find(arr[i]) == seen.end()) {
cout << arr[i] << " ";
seen.insert(arr[i]);
}
}
return 0;
}
Output
Array after removing duplicates: 1 2 3 4
Java Implementation
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 1, 4};
Set set = new LinkedHashSet<>();
for(int num : arr) {
set.add(num);
}
System.out.print("Array after removing duplicates: ");
for(int num : set) {
System.out.print(num + " ");
}
}
}
Output
Array after removing duplicates: 1 2 3 4
Python Implementation
arr = [1, 2, 3, 2, 1, 4]
result = []
seen = set()
for num in arr:
if num not in seen:
seen.add(num)
result.append(num)
print("Array after removing duplicates:", result)
Output
Array after removing duplicates: [1, 2, 3, 4]
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1, 2, 3, 2, 1, 4};
HashSet set = new HashSet();
Console.Write("Array after removing duplicates: ");
foreach(int num in arr) {
if(set.Add(num)) {
Console.Write(num + " ");
}
}
}
}
Output
Array after removing duplicates: 1 2 3 4
JavaScript Implementation
let arr = [1, 2, 3, 2, 1, 4];
let seen = new Set();
let result = [];
for (let num of arr) {
if (!seen.has(num)) {
seen.add(num);
result.push(num);
}
}
console.log("Array after removing duplicates:", result);
Output
Array after removing duplicates: [1, 2, 3, 4]
Common Mistakes to Avoid
- Removing elements while iterating incorrectly
- Losing original order
- Using sorting when not required
- Ignoring space constraints
Interview Variations
- Remove duplicates from sorted array
- Count duplicates
- Remove duplicates without extra space
- Find duplicate elements
Detailed Summary
Removing duplicate elements from an array is a fundamental data-cleaning and optimization task. By tracking previously seen values using auxiliary structures like sets, we can efficiently filter out repeated elements while preserving their original order. This problem introduces the practical use of hashing concepts and prepares the ground for more advanced topics such as frequency maps, intersection of arrays, and optimized searching techniques.
Next Problem in the Series
Move All Zeros to the End
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
