.png)
Find Duplicate Elements in an Array
Problem Statement
Given an array of n elements, find all the duplicate elements.
- Duplicates are elements that appear more than once.
- The goal is to identify all such elements efficiently.
- Arrays can contain any range of numbers, positive, negative, or zero.
Example 1
Input:
arr = [1, 2, 3, 2, 4, 3, 5]
Output:
[2, 3]
Explanation:
- Numbers 2 and 3 appear more than once in the array.
Example 2
Input:
arr = [5, 4, 6, 7, 4, 5, 5]
Output:
[4, 5]
Explanation:
- Numbers 4 appears twice, 5 appears three times.
Why This Problem Is Important
- Tests array traversal, hashing, and counting frequency.
- Useful for data validation, analytics, and duplicate elimination.
- Foundation for advanced problems like finding duplicates in O(1) space or arrays with constraints.
Approaches to Solve the Problem
- Using a Hash Map / Dictionary (Efficient) ✅
- Using Sorting (In-place / Less Extra Space) ✅
- Brute Force (Nested Loops, Not Recommended)
Approach 1: Using Hash Map / Dictionary
Idea
- Traverse the array and maintain a frequency map.
- For every element, increase its count in the map.
- After traversal, all elements with count > 1 are duplicates.
Time & Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(n)
C++ Implementation
#include
#include
#include
using namespace std;
int main() {
vector arr = {1, 2, 3, 2, 4, 3, 5};
unordered_map freq;
for(int num : arr) freq[num]++;
cout << "Duplicate elements: ";
for(auto it : freq)
if(it.second > 1) cout << it.first << " ";
}
Java Implementation
import java.util.*;
public class FindDuplicates {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 4, 3, 5};
HashMap freq = new HashMap<>();
for(int num : arr)
freq.put(num, freq.getOrDefault(num, 0) + 1);
System.out.print("Duplicate elements: ");
for(int key : freq.keySet())
if(freq.get(key) > 1) System.out.print(key + " ");
}
}
Python Implementation
arr = [1, 2, 3, 2, 4, 3, 5]
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
duplicates = [num for num,count in freq.items() if count > 1]
print("Duplicate elements:", duplicates)
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1, 2, 3, 2, 4, 3, 5};
Dictionary freq = new Dictionary();
foreach(int num in arr)
freq[num] = freq.GetValueOrDefault(num,0) + 1;
Console.Write("Duplicate elements: ");
foreach(var kvp in freq)
if(kvp.Value > 1) Console.Write(kvp.Key + " ");
}
}
JavaScript Implementation
let arr = [1,2,3,2,4,3,5];
let freq = {};
arr.forEach(num => freq[num] = (freq[num] || 0) + 1);
let duplicates = [];
for(let key in freq){
if(freq[key] > 1) duplicates.push(Number(key));
}
console.log("Duplicate elements:", duplicates);
Approach 2: Using Sorting
Idea
- Sort the array.
- Traverse the array and compare current element with next element.
- If they are equal, it is a duplicate.
Time & Space Complexity
- Time Complexity: O(n log n) (sorting)
- Space Complexity: O(1) if in-place sorting
Python Implementation (Sorting)
arr = [1,2,3,2,4,3,5]
arr.sort()
duplicates = []
for i in range(len(arr)-1):
if arr[i] == arr[i+1] and (len(duplicates)==0 or duplicates[-1] != arr[i]):
duplicates.append(arr[i])
print("Duplicate elements:", duplicates)
C++ Implementation (Sorting)
#include
#include
#include
using namespace std;
int main() {
vector arr = {1,2,3,2,4,3,5};
sort(arr.begin(), arr.end());
vector duplicates;
for(int i=0;i
Approach 3: Brute Force (Nested Loops)
Idea
- Compare every element with every other element in the array.
- If a match is found and it is not already in the duplicates list, add it.
- Not efficient for large arrays: O(n²) time complexity, O(1) extra space.
Time & Space Complexity
- Time Complexity: O(n²) (two nested loops)
- Space Complexity: O(1) if storing duplicates in a small array/list
Python Implementation
arr = [1, 2, 3, 2, 4, 3, 5]
duplicates = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j] and arr[i] not in duplicates:
duplicates.append(arr[i])
print("Duplicate elements:", duplicates)
Output:
Duplicate elements: [2, 3]
C++ Implementation
#include
#include
using namespace std;
int main() {
vector arr = {1, 2, 3, 2, 4, 3, 5};
vector duplicates;
for(int i = 0; i < arr.size(); i++){
for(int j = i + 1; j < arr.size(); j++){
if(arr[i] == arr[j]){
bool alreadyAdded = false;
for(int k = 0; k < duplicates.size(); k++){
if(duplicates[k] == arr[i]){
alreadyAdded = true;
break;
}
}
if(!alreadyAdded)
duplicates.push_back(arr[i]);
}
}
}
cout << "Duplicate elements: ";
for(int num : duplicates)
cout << num << " ";
}
Java Implementation
import java.util.*;
public class FindDuplicatesBruteForce {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 4, 3, 5};
ArrayList duplicates = new ArrayList<>();
for(int i = 0; i < arr.length; i++){
for(int j = i + 1; j < arr.length; j++){
if(arr[i] == arr[j] && !duplicates.contains(arr[i])){
duplicates.add(arr[i]);
}
}
}
System.out.println("Duplicate elements: " + duplicates);
}
}
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1, 2, 3, 2, 4, 3, 5};
List duplicates = new List();
for(int i = 0; i < arr.Length; i++){
for(int j = i + 1; j < arr.Length; j++){
if(arr[i] == arr[j] && !duplicates.Contains(arr[i])){
duplicates.Add(arr[i]);
}
}
}
Console.Write("Duplicate elements: ");
foreach(int num in duplicates)
Console.Write(num + " ");
}
}
JavaScript Implementation
let arr = [1, 2, 3, 2, 4, 3, 5];
let duplicates = [];
for(let i = 0; i < arr.length; i++){
for(let j = i + 1; j < arr.length; j++){
if(arr[i] === arr[j] && !duplicates.includes(arr[i])){
duplicates.push(arr[i]);
}
}
}
console.log("Duplicate elements:", duplicates);
✅ Summary of Approaches
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Hash Map / Dictionary | O(n) | O(n) | Most efficient |
| Sorting | O(n log n) | O(1) (in-place) | Works if modifying array is allowed |
| Brute Force (Nested Loops) | O(n²) | O(1) | Simple but slow, only for small arrays |
Finding duplicate elements is a classic array problem:
- Hash Map / Dictionary → Efficient, O(n) time and space
- Sorting → In-place, O(n log n) time, O(1) extra space
- Brute Force → Nested loops, O(n²), not recommended
Mastering this problem helps in data validation, array manipulation, and coding interview preparation.
.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)
