Find Repeating Elements in an Array: Three C++ Approaches

Three C++ methods solve the repeating-elements problem: brute-force with O(n²) time, sort-then-scan with O(n log n) time, and hash-based detection with O(n) time.

Placement tests from TCS NQT to AMCAT Automata treat this as a warm-up coding question. The correct answer is not just the code; it’s the trade-off reasoning: which approach you pick depends on whether you can afford O(n) extra space and whether the original element order needs to be preserved.

The Problem and Its Variants

Given an integer array, identify every element that appears more than once.

Standard example:

• Input: {1, 2, 3, 4, 2, 3, 5}
• Expected output: 2 and 3 (both appear twice)

Three edge cases worth checking before writing any solution:

• No duplicates: {1, 2, 3, 4, 5} — the algorithm must produce no output, not a false positive.
• All identical: {4, 4, 4, 4} — element 4 is a duplicate; it should be reported once, not three times.
• Single element: {7} — no pair comparison is possible; produce no output.

Related array-traversal problems that share this scanning pattern are covered in detail in the find smallest and largest element tutorial.

Approach 1: Brute-Force Nested Loops

For each element at index i, scan every element at index j where j > i. If arr[i] == arr[j], report arr[i] as a duplicate and move to the next i.

Algorithm

• Loop i from 0 to n-1.
• For each i, loop j from i+1 to n-1.
• If arr[i] == arr[j], print arr[i] and break the inner loop (prevents printing the same value multiple times when it appears three or more times).
• Continue until all i values are processed.

C++ Code

#include <iostream>
using namespace std;

void findDuplicatesBrute(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) {
                cout << arr[i] << "\n";
                break;
            }
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Repeating elements:\n";
    findDuplicatesBrute(arr, n);
    return 0;
}

Output:

Repeating elements:
2
3

Complexity

• Time: O(n²) — two nested loops, each up to n iterations.
• Space: O(1) — no auxiliary data structure.
• Best for: small arrays (under a few hundred elements) or when no extra memory is permitted and n log n time is not acceptable.

Approach 2: Sort Then Scan

Sorting the array groups equal elements into adjacent positions. One linear scan after sorting finds every adjacent pair.

Algorithm

• Sort the array using std::sort (O(n log n)).
• Scan from index 1 to n-1.
• If arr[i] == arr[i-1] and (i is 1 OR arr[i] != arr[i-2]), print arr[i]. The extra guard prevents reporting the same element again when it appears three or more times.

C++ Code

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

void findDuplicatesSort(int arr[], int n) {
    sort(arr, arr + n);  // O(n log n)
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1]) {
            // Print only on the first detection of each duplicate
            if (i == 1 || arr[i] != arr[i - 2]) {
                cout << arr[i] << "\n";
            }
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Repeating elements:\n";
    findDuplicatesSort(arr, n);
    return 0;
}

Output:

Repeating elements:
2
3

Complexity

• Time: O(n log n) — dominated by the sort step. The cppreference entry for std::sort documents this as an introsort (typically quicksort + heapsort fallback) with average O(n log n).
• Space: O(1) extra space — std::sort is in-place (excluding the internal recursion stack, which is O(log n) for introsort).
• Limitation: modifies the original array. If you need to preserve element order, either copy the array before sorting or use Approach 3.

Approach 3: Hash Set Detection

A single pass with an unordered_set checks membership in O(1) amortised time. Insert each element; if the element is already in the set, it is a duplicate.

Algorithm

• Create an empty unordered_set<int>.
• Scan from index 0 to n-1.
• If arr[i] is already in the set, print arr[i].
• Otherwise, insert arr[i] into the set.

C++ Code

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

void findDuplicatesHash(int arr[], int n) {
    unordered_set<int> seen;
    for (int i = 0; i < n; i++) {
        if (seen.count(arr[i])) {
            cout << arr[i] << "\n";
        } else {
            seen.insert(arr[i]);
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Repeating elements:\n";
    findDuplicatesHash(arr, n);
    return 0;
}

Output:

Repeating elements:
2
3

The cppreference documentation for std::unordered_set explains the amortised O(1) insert and lookup behaviour. In the worst case (hash collisions), lookup degrades to O(n), which is rare in practice with integer keys and a standard hash function.

Extension: Frequency Count with unordered_map

If the problem asks for exact repetition counts rather than a yes/no detection, replace unordered_set with unordered_map<int, int>:

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

void findDuplicatesCount(int arr[], int n) {
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
    for (auto& p : freq) {
        if (p.second > 1) {
            cout << p.first << " appears " << p.second << " times\n";
        }
    }
}

This extension does not change the O(n) time or O(n) space class.

Complexity

• Time: O(n) average — one pass, O(1) amortised per insert and lookup.
• Space: O(n) — the set holds at most n distinct elements.
• Best for: large arrays where time matters, when original order must be preserved, and when extra O(n) memory is acceptable.

Complexity Comparison and Placement Context

Approach	Time	Extra Space	Preserves Order?	Best Use Case
Brute-force nested loops	O(n²)	O(1)	Yes	Small arrays, no memory budget
Sort then scan	O(n log n)	O(1)	No	Medium arrays, no extra memory
Hash set	O(n) avg	O(n)	Yes	Large arrays, memory available

In placement tests, the expected answer depends on the interview tier:

• Service tier (TCS, Infosys, Wipro): brute-force is accepted if it produces the correct output. Time-limit constraints on automated judges are usually lenient for n under 1,000.
• Product and MNC technical rounds: expect the hash-set solution with an explicit O(n) justification. An interviewer who asks “can you do better?” after seeing brute-force wants to hear the hash-set approach by name.

For a broader look at which data-structure patterns come up most often across Indian technical rounds, see 20 most asked data structures interview questions. The same pattern of “brute-force vs. optimal” reasoning applies to linked-list, tree, and graph problems in that article.

Hash-based frequency counting (the O(n) mechanism in Approach 3) is also the same pattern behind token frequency tables in language models: count occurrences of each token across a corpus and report what repeats above a threshold. Moving from counting array duplicates to counting token occurrences in a text is a smaller conceptual jump than it appears. If you want to work with actual LLM internals at that level, TinkerLLM at ₹299 is a practical entry point.

Similar algorithm-structure patterns appear in string problems too. The palindrome check tutorial shows the same “two-pointer vs. reverse vs. hash” trade-off applied to a string input.