C++ Program to Find Duplicate Elements in Array

To find duplicate elements in an array in C++, use a loop to compare each element with others and print elements that appear more than once, like for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { cout << arr[i] << ' '; break; } }}.

Examples

Inputarr = {1, 2, 3, 2, 4, 5, 1}

OutputDuplicate elements are: 1 2

Inputarr = {10, 20, 30, 40, 50}

OutputNo duplicate elements found

Inputarr = {5, 5, 5, 5}

OutputDuplicate elements are: 5

How to Think About It

To find duplicates, check each element against all others to see if it appears more than once. Keep track of which duplicates you already found to avoid printing the same duplicate multiple times.

Algorithm

1

Get the input array and its size.

2

Create a way to track which elements are already identified as duplicates.

3

For each element, compare it with the rest of the elements in the array.

4

If a duplicate is found and not already recorded, print it and mark it as found.

5

If no duplicates are found, print a message saying so.

Code

cpp

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 2, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    bool foundDuplicate = false;

    cout << "Duplicate elements are: ";
    for (int i = 0; i < n; i++) {
        bool isDuplicate = false;
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) {
                isDuplicate = true;
                break;
            }
        }
        bool alreadyPrinted = false;
        for (int k = 0; k < i; k++) {
            if (arr[i] == arr[k]) {
                alreadyPrinted = true;
                break;
            }
        }
        if (isDuplicate && !alreadyPrinted) {
            cout << arr[i] << " ";
            foundDuplicate = true;
        }
    }

    if (!foundDuplicate) {
        cout << "No duplicate elements found";
    }

    cout << endl;
    return 0;
}

Output

Duplicate elements are: 1 2 

Dry Run

Let's trace the array {1, 2, 3, 2, 4, 5, 1} through the code to find duplicates.

1

Start with first element (1)

Check elements after index 0: found 1 again at index 6, mark as duplicate.

2

Check second element (2)

Check elements after index 1: found 2 again at index 3, mark as duplicate.

3

Check third element (3)

No duplicates found after index 2.

4

Check fourth element (2)

Already printed 2 as duplicate, skip.

5

Check fifth element (4)

No duplicates found after index 4.

6

Check sixth element (5)

No duplicates found after index 5.

7

Check seventh element (1)

Already printed 1 as duplicate, skip.

Index	Element	Duplicate Found?	Already Printed?
0	1	Yes	No
1	2	Yes	No
2	3	No	No
3	2	Yes	Yes
4	4	No	No
5	5	No	No
6	1	Yes	Yes

Why This Works

Step 1: Check each element with others

The code compares each element with all elements after it to find duplicates using arr[i] == arr[j].

Step 2: Avoid printing duplicates multiple times

Before printing, it checks if the duplicate was already printed by scanning earlier elements.

Step 3: Print duplicates or no duplicates message

If duplicates are found, they are printed; otherwise, a message says no duplicates exist.

Alternative Approaches

Using std::unordered_set

cpp

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 2, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    unordered_set<int> seen;
    unordered_set<int> duplicates;

    for (int i = 0; i < n; i++) {
        if (seen.find(arr[i]) != seen.end()) {
            duplicates.insert(arr[i]);
        } else {
            seen.insert(arr[i]);
        }
    }

    if (duplicates.empty()) {
        cout << "No duplicate elements found" << endl;
    } else {
        cout << "Duplicate elements are: ";
        for (int x : duplicates) {
            cout << x << " ";
        }
        cout << endl;
    }
    return 0;
}

This method is faster (O(n)) and simpler but uses extra memory for sets.

Sorting the array first

cpp

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 2, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    sort(arr, arr + n);
    bool foundDuplicate = false;

    cout << "Duplicate elements are: ";
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] == arr[i + 1]) {
            if (i == 0 || arr[i] != arr[i - 1]) {
                cout << arr[i] << " ";
                foundDuplicate = true;
            }
        }
    }

    if (!foundDuplicate) {
        cout << "No duplicate elements found";
    }
    cout << endl;
    return 0;
}

Sorting helps find duplicates by checking neighbors but changes original array order.

Complexity: O(n^2) time, O(1) space

Time Complexity

The nested loops compare each element with all others, resulting in O(n^2) time.

Space Complexity

No extra space is used except a few boolean flags, so space complexity is O(1).

Which Approach is Fastest?

Using an unordered_set reduces time to O(n) but uses extra space O(n). Sorting is O(n log n) but modifies the array.

Approach	Time	Space	Best For
Nested loops	O(n^2)	O(1)	Small arrays, no extra memory
Hash set	O(n)	O(n)	Large arrays, fast detection
Sorting	O(n log n)	O(1)	When array order can be changed