Find All Duplicate Elements in an Array (C++)

Source: Dev.to

Problem Summary

Identify all elements that appear more than once in an array and report each duplicate only once.

Example

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

Approach 1: Frequency Array

Use this method when the range of possible values is known and relatively small.

#include 
using namespace std;

int main() {
    vector n = {1, 2, 3, 2, 4, 1};
    vector out;
    vector tracker(100, 0);   // adjust size according to the value range

    for (int x : n) tracker[x]++;

    for (size_t i = 0; i  1) {
            out.push_back(static_cast(i));
        }
    }
    // `out` now contains the duplicate values
}

Complexity

• Time: O(n + k) where n is the number of elements and k is the size of the value range.
• Space: O(k) for the frequency array.

When to Use

• The value range is known and small, allowing a compact frequency array.
• You need the fastest possible lookup.

Approach 2: Using unordered_map

This method works for any range of values.

#include 
#include 
using namespace std;

int main() {
    vector n = {1, 2, 3, 2, 4, 1};
    vector out;
    unordered_map tracker;

    for (int x : n) tracker[x]++;

    for (const auto& it : tracker) {
        if (it.second > 1) {
            out.push_back(it.first);
        }
    }
    // `out` now contains the duplicate values
}

Complexity

• Time: O(n) on average (hash table operations).
• Space: O(n + z) where z is the number of distinct duplicate values.

When to Use

• The range of possible values is unknown or large.
• You prefer a flexible solution that adapts to any input domain.

Key Comparison

Final Takeaway

Both approaches correctly identify duplicate elements.
Choose the frequency‑array method when the value range is limited and you need maximum speed.
Choose the unordered_map method when the range is unknown or large, accepting a modest increase in space usage.

Understanding why you select an approach is often more important than the code itself.